[백준] 2660번 회장뽑기

2660번 회장 뽑기

---

1. 이해하기

• 자신을 기점으로 가입한 회원이 얼마나 멀리 떨어져있는지를 구하는 문제이다.
• bfs를 이용하여 문제를 풀 수 있다.
• dfs로는 힘든 것이 사이클이 발생할 경우 제일 깊은 노드가 무엇인지 찾기 힘들기 때문이다.

---

2. 구현하기

• 먼저 현재 위치와 얼마나 멀리 떨어져있는지를 저장할 Pair 클래스를 선언한다.

  static class Pair {
        int x, depth;
  
        Pair(int x, int depth) {
            this.x = x;
            this.depth = depth;
        }
    }

• bfs(start)

  • bfs를 이용하여 자신과 얼마나 멀리 떨어져 있는지를 구한다.

  • 한번 멀어질 때마다 현재 depth+1을 기록해줘서 가장 멀리 떨어진 사람의 depth가 몇인지 구해준다.

    static void bfs(int start) {
      Queue<Pair> q = new LinkedList<>();
      q.add(new Pair(start,0));
      visited = new boolean[N+1];
      visited[start] = true;
      int max = 0;
    
      while(!q.isEmpty()) {
          Pair here = q.poll();
          for(int i = 1; i <= N; i++) {
              if(adj[here.x][i] == 0 || visited[i]) continue;
              q.add(new Pair(i,here.depth+1));
              max = (max < here.depth+1) ? here.depth+1 : max;
              visited[i] = true;
          }
      }
    
      depth[start] = max;
    }

---

3. 전체코드

package algo;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Acm2660_회장뽑기 {
    static int N;
    static int[][] adj;
    static int[] depth;
    static boolean[] visited;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        adj = new int[N+1][N+1];
        depth = new int[N+1];
        while(true) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            if(u == -1 && v == -1)
                break;
            adj[u][v] = adj[v][u] = 1;
        }

        int min = 100;
        for(int i = 1; i <= N; i++) {
            bfs(i);
            min = (min > depth[i]) ? depth[i] : min;
        }

        ArrayList<Integer> ans = new ArrayList<>();
        for(int i = 1; i <= N; i++) {
            if(min == depth[i])
                ans.add(i);
        }

        System.out.println(min + " " + ans.size());
        for(int ele: ans)
            System.out.print(ele+" ");
        System.out.println();
        sc.close();
    }

    static void bfs(int start) {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(start,0));
        visited = new boolean[N+1];
        visited[start] = true;
        int max = 0;

        while(!q.isEmpty()) {
            Pair here = q.poll();
            for(int i = 1; i <= N; i++) {
                if(adj[here.x][i] == 0 || visited[i]) continue;
                q.add(new Pair(i,here.depth+1));
                max = (max < here.depth+1) ? here.depth+1 : max;
                visited[i] = true;
            }
        }

        depth[start] = max;
    }

    static class Pair {
        int x, depth;

        Pair(int x, int depth) {
            this.x = x;
            this.depth = depth;
        }
    }
}