[백준 - 12896번] 스크루지 민호 -Java

문제 링크

https://www.acmicpc.net/problem/12896

문제

티어: 골드 2
알고리즘: dfs
구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을 들이고 싶어서 N - 1 개의 도로를 이용해 모든 도시들 사이에는 단 한개의 경로만이 존재하도록 도시를 세웠다.

도시를 세울 당시에 소방서를 여러개 건설하는 것이 아까웠던 스쿠르지 민호는 단 하나의 도시에 소방서를 건설하기로 했다. 하지만 최소한의 양심이 있어서인지 소방서는 최적의 위치가 될 수 있는 도시에 건설하기로 했다. 최적의 위치라는 것은 소방서에서 소방차가 출동해 다른 도시에 도착을 할 때 이동해야 하는 거리중의 최대가 최소가 되는 지점을 의미한다. 편의상 같은 도시 내에서 이동하는 거리는 없다고 생각하며 한 도시에서 다른 도시로 연결된 도로는 거리가 1이라고 생각한다.

천나라에 있는 도시의 수와 도로들의 연결 상태가 주어질 때 최적의 위치에 설치된 소방서에서 소방차가 출동해 다른 도시에 도착할 때 이동해야하는 거리들 중 최대 거리를 구하는 프로그램을 작성하자.

입력

첫째 줄에는 천나라에 있는 도시의 수 N (2 ≤ N ≤ 100,000) 이 주어진다. 다음 N - 1 줄에 걸쳐 도시들의 연결 상태가 주어진다.

각각의 줄에는 공백을 기준으로 세개의 숫자가 u, v (1 ≤ u, v ≤ N) 가 주어지는데 이는 도시 u와 v가 양방향 도로로 연결이 되어 있다는 것을 의미한다.

출력

첫째 줄에 최적의 위치에 설치된 소방서에서 소방차가 출동해 다른 도시에 도착할 때까지 이동해야하는 거리들 중 최댓값을 출력한다.

풀이

최적의 위치에 설치된 소방서에서 소방차가 출동해 다른 도시에 도착할 때까지 이동해야 하는 거리들 중 최댓값을 출력해야 한다.

다른 사람이 푼 걸 보니 억지스러운 풀이일 수 있겠지만, 내가 푼 방법을 공유해 보겠다.

5
4 5
4 2
2 3
1 2

이렇게 예제가 있을 때

1에서부터 시작해 보면, 1은 모든 경로를 방문하고, 그 중 max 값을 가져오면 된다.

나머지 2 ~ 5도 단순히 똑같은 과정을 거친다면, 그냥 완탐이랑 다를 게 없고, 시간 초과가 날 것이다.

생각해 보면, 1에서 2를 방문하고, 2에서는 1을 제외한 나머지를 방문하게 된다.
이때 2에서 출발한 모든 경로에 값들을 비교해 max 값을 가지고 있다면, 나중에 2로 들어오는 경로는 그 이후를 탐색하지 않아도 된다.

예를 들어
2 -> 3 (2에서 3으로 갔을 때 max 값)
2 -> 4 (2에서 4으로 갔을 때 max 값)
2 -> 1 (2에서 1으로 갔을 때 max 값)
을 구해놓았다고 했을 때

나중에 4에서 출발해 2로 들어갔을 때 구해놓은 2 -> 3, 2 -> 1를 비교해 max 값을 취하면 되기 때문에 이후 탐색이 발생하지 않는다.

그런데 따져줘야 할 부분이 많기 때문에 구현이 까다롭다.

예를 들어 단순히 2에서 세 개의 max값 중 하나의 max값 만을 가지고 있다면, 그 max가 항상 답이 되진 않는다. (2 -> 4가 max라면, 4 -> 2로 갔을 때 2 -> 4의 max 값을 얻음)

그렇다고 모든 max를 매번 비교하는 것도 시간 초과가 발생할 것이다.

그래서 나는 우선순위 큐를 활용해서 모든 max값을 넣어놓고, 만약 peek()에 값이 2 -> 4라면 그다음으로 큰 값을 취하게끔 구현했다.

그래서 항상 가장 큰 두 개의 max만이 각 node에서 필요하지만, 간단하게 pq를 활용했다.

여기서 추가적으로 체크해야 될 부분은

• 현재 노드에서 모든 노드를 방문했는지 체크 그렇지 않다면 일단 모든 노드를 방문해야 한다.
• 첫 번째 시작인 경우(bA가 0인 경우)는 pq의 peek()가 답임 (말 그대로 시작점이기 때문에)
• pq의 size()에 따라 return값이 달라짐.

이 경우를 잘 따져줘서 구현을 해줘야 한다. 그렇게 많진 않은데 놓칠 수 있는 부분이 좀 있기 때문에 유의해서 구현을 해야할 것이다.

자세한 구현은 코드를 참고하길 바란다.

소스 코드

import java.io.*;
import java.util.*;

class Node implements Comparable<Node> {
    int b, max;
    Node(int b, int max) {
        this.b = b;
        this.max = max;
    }
    
    @Override
    public int compareTo(Node o) {
        if(this.max < o.max) {
            return 1;
        } else if(this.max > o.max) {
            return -1;
        }
        return 0;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
      for(int i=0; i<=N; i++) {
          graph.add(new ArrayList<>());
      }
      
      for(int i=0; i<N - 1; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken());
          int b = Integer.parseInt(st.nextToken());
          graph.get(a).add(b);
          graph.get(b).add(a);
      }
      
      HashMap<Integer, Boolean>[] visited = new HashMap[N + 1];
      PriorityQueue<Node>[] nodePqs = new PriorityQueue[N + 1];
      for(int i=1; i<=N; i++) {
          visited[i] = new HashMap<>();
          nodePqs[i] = new PriorityQueue<>();
      }
      
      int answer = Integer.MAX_VALUE;
      for(int i=1; i<=N; i++) {
          int result = dfs(0, i, graph, visited, nodePqs);
          answer = Math.min(answer, result);
      }
      System.out.println(answer);
  }
  
  static int dfs(int bA, int a, ArrayList<ArrayList<Integer>> graph, HashMap<Integer, Boolean>[] visited, PriorityQueue<Node>[] nodePqs) {
      int fm = findMax(bA, a, visited, nodePqs);
      if(fm != -1) {
          return fm;
      }
      //a에서 전체 노드를 방문하지 않음.
      for(int i=0; i<graph.get(a).size(); i++) {
          int b = graph.get(a).get(i);
          if(b != bA && visited[a].get(b) == null) {
              //방문하지 않았다면.
              int v = dfs(a, b, graph, visited, nodePqs) + 1;
              visited[a].put(b, true); //방문 체크
              nodePqs[a].add(new Node(b, v));
          }
      }
      
      if(bA == 0 || visited[a].get(bA) != null) {
          visited[a].put(a, true);
      }
      
      if(nodePqs[a].size() == 0) {
          return 0;
      }
      
      Node n1 = nodePqs[a].peek();
      if(n1.b != bA) {
          return n1.max;
      }
      
      if(nodePqs[a].size() == 1) {
          return 0;
      }
      
      nodePqs[a].poll();
      Node n2 = nodePqs[a].peek();
      nodePqs[a].add(n1);
      return n2.max;
  }
  
  static int findMax(int bA, int a, HashMap<Integer, Boolean>[] visited, PriorityQueue<Node>[] nodePqs) {
      if(visited[a].get(a) != null) {
          //a에서 전체 노드를 방문했음을 의미한다.
          if(bA == 0) {
              return nodePqs[a].peek().max;
          }
          
          if(nodePqs[a].size() == 1) {
              //bA에서 들어오는 경로밖에 없음.
              return 0;
          } else {
              //여러 경로가 있다는 의미.
              Node n1 = nodePqs[a].peek();
              if(n1.b != bA) {
                  return n1.max;
              }
              
              nodePqs[a].poll();
              Node n2 = nodePqs[a].peek();
              nodePqs[a].add(n1);
              return n2.max;
          }
      }
      return -1;
  }
}