[SWEA 1238] [S/W 문제해결 기본] 10일차 - Contact

문제

• SWEA 1238번
• 문제의 저작권은 SW Expert Academy에 있습니다.

접근방식

이 문제는 그래프를 탐색하므로 BFS, DFS 두가지 방법으로 풀 수 있다.

1. BFS

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Swea_1238 {

	static StringTokenizer st;
	static final int MAX = 100; // 최대 연락인원
	static int N; // 데이터의 길이
	static int start; // 시작점
	static boolean[][] adjMatrix; // 인접행렬
	static int Ans;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		for (int tc = 1; tc <= 10; tc++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			start = Integer.parseInt(st.nextToken());

			adjMatrix = new boolean[MAX + 1][MAX + 1];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N / 2; i++) { // from, to로 나눠야함
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				adjMatrix[from][to] = true; // 인접표시
			}

			// start정점부터 탐색 시작
			bfs();
			System.out.println("#" + tc + " " + Ans);
		}
	}

	public static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		int visited[] = new int[MAX + 1];
		for(int i=1; i<=MAX; i++) visited[i] = -1; //방문x -1

		int current = start; // 현재 정점
		int size, level = 0; // 큐 사이즈, 레벨
		queue.offer(current);
		visited[current] = level;

		while (!queue.isEmpty()) { // 큐가 비어있지 않다면
			size = queue.size();
			level++;
			while (size-- > 0) { // 레벨단위로 돌리기
				current = queue.poll();
				for (int j = 1; j <= MAX; j++) {
					if (adjMatrix[current][j] && visited[j] == -1) { // 인접하고 방문x
						queue.offer(j);
						visited[j] = level;
					}
				}
			}
		}
		
		Ans = 0;
		//방문한 정점 중 가장 높은 레벨 추출
		for(int i=1; i<=MAX; i++) {
			if((visited[i] == level-1) && (i > Ans)) {
				Ans = i;
			}
		}
	}
}