[SWEA] 1238. Contact

문제

SWEA 1238. Contact

풀이

해당 문제는 정점의 최대 개수가 101개(1~100)이기 때문에 인접리스트는 사용하지 않고 인접배열과 bfs()를 사용했다.
while에서 queue의 size만큼 반복문을 돌고
방문한 지점은 visited 처리하여 방문하지 않은 곳들만 queue에 넣도록 하였다.

JAVA코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Solution
{
    
    static boolean[][] map;
	static int N, start;
	static int ans;
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		for (int tc = 1; tc <= 10; tc++) {

			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			start = Integer.parseInt(st.nextToken());

			map = new boolean[101][101];
			ans = Integer.MIN_VALUE;

			st = new StringTokenizer(br.readLine());

			for (int i = 0; i < N / 2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				map[from][to] = true;
			}

			bfs();

			System.out.println("#" + tc + " " + ans);
		}
	}

	public static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		boolean[] visited = new boolean[101];

		queue.offer(start);
		visited[start] = true;
		int max = -1;
		while (!queue.isEmpty()) {
			int size = queue.size();
			max = -1;

			for (int s = 0; s < size; s++) {

				int current = queue.poll();
				max = max < current ? current : max;

				for (int i = 1; i < map[current].length; i++) {
					if (map[current][i] && !visited[i]) {
						queue.offer(i);
						visited[i] = true;
					}
				}

			}
			ans=max;
		}
	}
}