2660_회장 뽑기

사용 알고리즘: bfs

사용 언어: java

 

import java.util.*;

public class Main_bj_2660_회장뽑기 {
    static int n; //총 인원 수
    static ArrayList<Integer>[] al ; //인접 리스트
    static int score ;
    static LinkedList<Integer> ll = new LinkedList<>(); //회장 후보 저장

    public static void main(String[] args) {
        input_2660();
        score = n; //나올 수 있는 최대 점수, 여기서 min 값을 찾기

        for (int i = 1; i < n+1; i++) {
            int chonsu = bfs_2660(i);
            if(score > chonsu) {
                score = chonsu;
                ll.clear();
                ll.add(i);
            }
            else if (score == chonsu) {
                ll.add(i);
            }
        }

        // score 출력
        System.out.println(score+" "+ll.size());
        // ll 출력
        for (int i : ll) {
            System.out.print(i+" ");
        }
    }

    private static int bfs_2660(int candidate) {
        boolean[] visited = new boolean[n+1];
        visited[candidate] = true;
        int maxChonsu = 0;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {candidate, 0});

        while (!q.isEmpty()) {
            int[] p = q.poll();
            maxChonsu = Math.max(maxChonsu, p[1]);

            for (int neighbor : al[p[0]]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.add(new int[] {neighbor, p[1]+1});
                }
            }
        }

//        System.out.println("candidate: "+candidate+" maxChonsu: "+maxChonsu);
        return maxChonsu;
    }

    private static void input_2660() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        al = new ArrayList[n+1]; //0인덱스 사용 x
        for (int i = 0; i < n+1; i++) {
            al[i] = new ArrayList<>();
        }

        while (true) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(a==-1 && b==-1) break;

            al[a].add(b);
            al[b].add(a);
        }
    }
}

 

 

!!

중간 다리를 건너서 아는 사람의 아는 사람은 아는 사람이다 문제 = 플로이드-워셜

인 경우가 대부분이라서 처음엔 이것도 그 문제인가? 했다.

그런데 다리를 건널 때마다 일종의 가중치를 부여해야 하는 것이어서 bfs가 맞다.

문제에서 최대 50명까지라고 했기 때문에 bfs를 써도 된다.