[백준] 2660번 : 회장뽑기

2660번: 회장뽑기

---

[BFS * n]

각 사람의 친구 관계를 인접 리스트에 저장.

n명에 대하여 BFS를 수행하였다. 이 때 Queue에 들어갈 원소는 2개이다. i 번째 사람, 그리고 1점에 해당하는 친구인지, 2점에 해당하는 친구인지, 혹은 그 이상 점수에 해당하는 친구인지...

 

BFS를 수행하며 친구의 최대값을 저장하고 있다가 BFS의 while문을 빠져나갈 때 저장하고 있던 최대값을 그 사람의 점수를 저장하는 배열 person[]에 담는다. 그리고 저장된 최대값들 중 가장 작은 값(min)을 따로 저장하여 둔다. 그렇게 n번의 BFS를 돌고나면 모든 사람에 대해 각 사람이 몇 점인지 알 수 있게된다.

 

person[]에 대해 n회 루프를 돌며 값이 min인 사람이 몇 명인지, 그 사람들의 인덱스를 저장해서 결과부분에 출력한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Elem{
        int tg, score;
        
        public Elem(int t, int sc){
            tg=t; 
            score=sc;
        }
    }
    static List<Integer>[] list = new ArrayList[51];
    static boolean[] visit;
    static int[] score = new int[51];
    static int min = 1000000000;

    static void BFS(int s, int n){

        Queue<Elem> Q = new LinkedList<>();
        visit = new boolean[n+1];
        int result = 0;

        visit[s] = true;
        Q.add(new Elem(s, 0));

        while(!Q.isEmpty()){
            Elem e = Q.poll();
            int cur = e.tg;
            int score = e.score;

            result = Math.max(score, result);

            for(int next:list[cur])
                if(!visit[next]){
                    visit[next] = true;
                    Q.add(new Elem(next, score + 1));
                }
        }
        min = Math.min(min, result);
        score[s] = result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }

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

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            if(v1 == -1) break;

            list[v1].add(v2);
            list[v2].add(v1);
        }

        for(int i=1; i<=n; i++)
            BFS(i, n);

        int cnt = 0;
        int[] person = new int[n+1];
        
        for(int i=1, j=0; i<=n; i++)
            if(score[i] == min) {
                cnt++;
                person[j++] = i;
            }

	//결과 출력
        System.out.println(min + " " + cnt);
        for(int i=0; person[i] != 0; i++)
            System.out.print(person[i] + " ");
    }
}