SWEA1238 Contact

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.Scanner;
import java.util.StringTokenizer;

public class Solution {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int N;
	static int[] visited;

	public static void bfs(int[][] adjMatrix, int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		visited = new int[101];
		
		queue.offer(start);
		visited[start] = 1;
		
		while(!queue.isEmpty()) {
			int current = queue.poll();
			//System.out.print(current + " ");
			
			// current 정점의 인접정점 처리(단, 방문하지 않은 인접정점만)
			for(int j = 1; j < 101; j++) {
				if(visited[j] == 0 && adjMatrix[current][j] > 0) {
					queue.offer(j);
					visited[j] = visited[current] + 1;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		for (int tc = 1; tc <= 10; tc++) {
			st = new StringTokenizer(br.readLine(), " ");
			int C = Integer.parseInt(st.nextToken());
			int V = Integer.parseInt(st.nextToken());
			int[][] adjMatrix = new int[101][101];

			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < C / 2; i++) {
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				adjMatrix[from][to] = 1;
			}
			bfs(adjMatrix, V);
			int max = 0, idx = 0;
			for(int i = 1; i < 101; i++) {
				if(visited[i] >= max) {
					max = visited[i];
					idx = i;
				}
			}
			
			bw.append("#" + tc + " " + idx + "\n");

		}
        bw.flush();
	}
}