[백준]12896: 스크루지 민호 - JAVA

[백준]12896: 스크루지 민호

12896번: 스크루지 민호

풀이

🪑 탐색과 관련된 문제로 DFS를 사용하여 풀었다. 문제를 잘 이해하는게 중요한 문제 였던 것 같다.

 

📝 문제의 조건을 살펴보자!

• N개의 도시를 N-1개의 도로로 연결하며 도로 사이에는 단 한개의 경로만이 존재한다. (트리이다!)
• 최적의 위치는 소방서에서 다른 도시로 가는 이동 거리 중에 최대가 최소가 되는 지점이다.
• 도시 간의 거리는 모두 1이다.
• 도로는 양방향으로 연결되어 있다.
• 최적의 위치에서 다른 도시에 도착할 때 이동 거리들 중 최대 거리를 구한다.

 

 

🙋‍♀️ 문제를 완벽하게 이해하기 위해 그림을 그려보자! 예제 1을 살펴보자.

 

🔹 문제에서 알 수 있듯이 도시들은 트리 구조로 연결되어 있다. 예제 1의 정보로 트리를 그려보자.

• 이때 모든 도시간의 거리는 1이다.

 

 

🔹 먼저, 구해야 하는 조건인 소방서에서 소방차가 출동해 다른 도시에 도착을 할 때 이동해야하는 거리 중의 최대가 최소가 되는 지점임을 생각해 보자.

• 먼저 이동 거리중의 최대를 구하는 방법을 생각해 보자.
• 이동 거리중의 최대가 되기 위해서는 트리 내에서 가장 먼 노드간의 거리를 구하면 된다..!
• 트리 내에서 가장 먼 노드간의 거리 -> 트리의 지름 -> https://moonsbeen.tistory.com/101 이 문제를 참고하자!
• 가장 먼 노드간의 거리를 구하기 위해서 임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구해주면 된다! 이 탐색 과정은 DFS를 활용했다.

• 위의 방법으로 가장 먼 노드간의 거리를 구하면 빨간색으로 선택된 경로가 될 것이다! (거리는 3)

 

 

🔹 가장 먼 노드간의 거리를 구했 다면 이제 먼 노드간의 루트 중에서 최소가 되는 지점을 구해보자.

• 직관적으로 생각해 보았을때 5-4-2-3의 경로 중에서 한 장소에 소방서를 설치한다고 생각 했을때, 모든 노드에서 해당 노드까지의 거리가 최소가 될 수 있는 지점은 2 또는 4가 된다.
• 2라고 생각하면 1->2는 1이고, 5->2는 2이고, 4->2는 1이고 3->2는 2이므로 원하는 결과 값은 2가 된다.
• 만약 5라고 생각하면 1->5는 3이고, 2->5는 2이고, 4->5는 1이고, 3->5는 3이므로 결과 값은 3이 된다.
• 이때 소방서를 2에 설치했을때의 최대 값은 2가 더 작은 거리가 되므로 소방서를 5에 설치하는 경우는 답이 될 수 없음을 알 수 있다.
• 그럼 최소가 될 수 있는 지점을 어떻게 고를 수 있을까? 

 

 

🔹 구한 루트에서 최소가 될 수 있는 지점을 고르자!

• 소방서를 2나 4에 설치한다고 하면 원하는 결과 값이 2가 나온다는 것을 위에서 확인해 보았다. 이 2라는 값은 어떻게 도출해 낼 수 있을까?
• 생각해 보면 되게 간단하다. 도시간의 거리는 모두 1이다. 직관적으로 생각해 보면 해당 경로의 중앙에 있는 노드를 선택하면 정답이 된다.
• 중앙에 있는 노드를 선택해야 가장 먼 노드 에서 거리를 계산해 보아도 가장 최적의 거리가 된다.
• 즉, 가장 먼 노드를 구하고, 그 노드간의 거리의 절반을 계산해 주면 우리가 원하는 정답이 된다! 이때 최대 값 중에서 최소값을 원하므로 식으로 표현하면 다음과 같다.
  • (1 + max) / 2

 

 

코드

//12896: 스크루지 민호
import java.io.*;
import java.util.*;
 
public class Main {
    
    static int n, max, node;
    static ArrayList<Node>[] list;
    static boolean[] visited;
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bf.readLine());
 
        list = new ArrayList[n + 1];
        for(int i = 0; i < n + 1; i++) {
            list[i] = new ArrayList<>();
        }
 
        for(int i = 0; i < n - 1; i++) {
            String str = bf.readLine();
            StringTokenizer st = new StringTokenizer(str);
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list[s].add(new Node(e, 1));
            list[e].add(new Node(s, 1));
        }
        //입력 끝
 
        //임의의 노드(1)에서 다른 노드로 가는 최대 거리와 그 거리에 있는 노드를 구한다.
        max = -1;
        visited = new boolean[n + 1];
        dfs(1, 0);
 
        //위에서 찾은 노드에서 가장 먼 노드로 가는 거리를 구한다.
        max = -1;
        visited = new boolean[n + 1];
        dfs(node, 0);
 
        System.out.println((1 + max) / 2);
    }
 
    public static void dfs(int x, int len) {
        if(max < len) {
            max = len;
            node = x;
        }
        visited[x] = true;
 
        for(int i = 0; i < list[x].size(); i++) {
            Node next = list[x].get(i);
            if(!visited[next.end]) {
                dfs(next.end, len + next.cost);
                visited[x] = true;
            }
        }
    }
 
    public static class Node {
        int end, cost;
 
        public Node(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }
    }
}