백준 2660번 회장뽑기 G5 - BFS

 

회장이 될 상이구나.

 

 

문제를 한참 읽은 것 같다. 

친구의친구의친구의..친구의..ㅊ.ㄱ..ㅇ...

정리하자면 친구인 사이가 많을수록 점수가 낮다. 

• 친구 -> 1점
• 친구의 친구 -> 2점
• 친구의 친구의 친구 -> 3점
• ... 

점수가 낮을수록 친구가 많다는 뜻 이므로 회장점수가 가장 높다고 판단한다.

예제를 간단히 그래프로 나타냈을때 

 

이처럼 된다.

주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

그렇다면 깊이자나. 깊이. 탐색하면 끝이네.

 

다만 회장후보의 점수와 후보 수를 출력해야하고, 후보자들을 출력해야 하므로 정렬도 필요하다.

가보자고

 

코드 흐름

1. 먼저 각 사람의 회장 점수를 계산합니다. 이 과정에서 가장 높은 회장점수를 찾아 메모리를 아낍니다.
2. 정리한 회장 점수를 통해서 회장 후보를 리스트에 담아줍니다.
3. 이후 sort를 통해 오름차순으로 정리하고 출력하면 꿑

 

import java.io.*;
import java.util.*;
 
public class Main { // Boj_2660_회장뽑기
    static int N;
    static boolean[][] arr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        arr = new boolean[N + 1][N + 1];
 
        // Input processing
        while (true) {
            st = new StringTokenizer(br.readLine());
            int n_1 = Integer.parseInt(st.nextToken());
            int n_2 = Integer.parseInt(st.nextToken());
            if (n_1 == -1 && n_2 == -1) {
                break;
            }
            arr[n_1][n_2] = true;
            arr[n_2][n_1] = true;
        }
 
        int min = Integer.MAX_VALUE;
        List<int[]> list = new ArrayList<>(); // 회장 점수 정리
        for (int i = 1; i <= N; i++) {
            int depth = bfs(i);
            list.add(new int[]{i, depth});
            min = Math.min(min, depth);
        }
 
        List<Integer> answer = new ArrayList<>(); // 회장후보
        for (int[] result : list) {
            if (result[1] == min) {
                answer.add(result[0]);
            }
        }
        Collections.sort(answer);
 
        sb.append(min).append(" ").append(answer.size()).append("\n");
        for (int n : answer) {
            sb.append(n).append(" ");
        }
        System.out.println(sb.toString());
    }
 
    public static int bfs(int start) {
        boolean[] visited = new boolean[N + 1];
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{start, 0});
        visited[start] = true;
        int maxDepth = 0;
 
        while (!que.isEmpty()) {
            int[] current = que.poll();
            int node = current[0];
            int depth = current[1];
            maxDepth = Math.max(maxDepth, depth);
            for (int i = 1; i <= N; i++) {
                if (arr[node][i] && !visited[i]) {
                    visited[i] = true;
                    que.add(new int[]{i, depth + 1});
                }
            }
        }
        return maxDepth;
    }
}