[백준] 2660번 : 회장뽑기

문제

 

 

접근 방식

한 사람이 모든 사람을 친구의 친구의 친구...의 친구 까지 걸치고 걸쳐

모두 알 수 있다고 가정 했을 때

모든 사람을 알기 위해 필요한 단계가 가장 짧은 사람을 구해야 한다.

1 2
2 3
3 4
4 5
2 4
5 3

 

위와 같은 관계가 주어졌을 때 2번 사람의 경우를 살펴보면 아래와 같다.

본인
2

친구
1 3 4

친구의 친구
5

 

2번 자기 자신과 직접적으로 친구 관계인 1, 3, 4번이 있고

5번은 3번의 친구니 친구의 친구 관계이고

2번이 모든 사람을 알기 위해 필요한 단계는 친구의 친구까지다.

 

즉, 본인 0단계, 친구 1단계, 친구의 친구 2단계로

2단계만 거치면 모든 사람을 알 수 있다.

 

이때 조심해야 할 점은 2번이 5번을 알 수 있는 방법이 두 가지인데

첫 번째는 2 >> 3 >> 4 >> 5 순서로 총 3단계를 걸치는 것이고

두 번째는 2 >> 3 >> 5 순서로 총 2단계를 걸치는 것이다.

 

이 중에서 가장 짧은 2단계를 선택해야 하므로

이미 방문한 곳이라도 더 빨리 방문할 수 있다면

기존에 기록해두었던 3단계를 2단계로 바꿔주면 된다.

 

 

풀이

public class Main {

	private static int n;
	private static int max;
	private static ArrayList<ArrayList<Integer>> near = new ArrayList<>();
	private static int[] scores;
	private static int[] friends;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());
		scores = new int[n + 1];
		friends = new int[n + 1];
		int min = n + 1;
		int count = 0;

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		while (true) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			if (x == y && x == -1) break;

			near.get(x).add(y);
			near.get(y).add(x);
		}

		for (int i = 1; i <= n; i++) {
			Arrays.fill(friends, -1);
			dfs(i, -1);
			max = 0;

			for (int j = 1; j <= n; j++) {
				max = Math.max(friends[j], max);
			}

			scores[i] = max;

			if (min > max) {
				count = 1;
				min = max;
			} else if (min == max) {
				count++;
			}
		}

		sb.append(min).append(" ").append(count).append("\n");
		for (int i = 1; i <= n; i++) {
			if (scores[i] == min) sb.append(i).append(" ");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur, int prev) {
		int score = prev + 1;
		friends[cur] = score;

		for (int next : near.get(cur)) {
			if (friends[next] != -1) {
				if (friends[next] > score + 1) {
					dfs(next, score);
				}
				continue;
			}
			dfs(next, score);
		}
	}
}