[Boj_19542] 전단지 돌리기

📎 문제 링크

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

 

▸ 문제

현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가 D 이하인 모든 노드에 전단지를 돌릴 수 있다.

날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.

 

▸ 입력

첫번째 줄에는 노드의 개수 N(1≤N≤100 000)과 케니소프트의 위치 S(1≤S≤N), 힘 D(0≤D≤N)이 주어진다.

두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드가 연결되어 있음을 의미한다. (1≤x,y≤N, x≠y)

주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 1이다.

 

▸ 출력

현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 3
• 🔔  문제 유형 : 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

트리 형태의 맵에서 전단지를 배포할 때, 최소한으로 이동하는 거리를 구하는 문제이다.

문제에서 현민이는 거리가 D 이하인 모든 노드에 전단지를 직접 방문하지 않고도 배포할 수 있다.
즉, 리프 노드에서부터 거리가 D를 초과하는 노드들만 직접 방문하면 된다.

 

1️⃣ DFS 탐색을 통해 각 노드의 최대 Depth를 계산한다.

• 각 노드에서 가장 깊은 노드까지의 거리(Depth)를 구한다.
• DFS를 수행하면서, 현재 노드의 Depth를 자식 노드 중 최대 Depth+1로 갱신한다.

 

2️⃣ 깊이가 D를 초과하는 노드까지 이동해야 한다.

• DFS 탐색 과정에서, Depth 값이 D를 초과하는 노드까지 이동해야 하므로 해당 노드를 카운트한다.
• 이 노드들은 현민이가 직접 이동해야 하므로 cnt 값을 증가시킨다.

 

3️⃣ 왕복 거리를 계산한다.

• 모든 노드에 전단지를 돌리고 다시 출발 지점으로 돌아와야 하므로, 이동해야 하는 간선 개수에 2를 곱해 왕복 거리를 구한다.

 

🔍 참고

트리는 사이클이 없는 연결 그래프이므로, 특정 노드에서 다른 노드까지의 최단 거리는 간선의 개수로 표현된다.

따라서, 필요한 방문 횟수를 구한 후, 2를 곱하여 왕복 거리를 구할 수 있다.

 

예제 입력 1을 예시로 들어보면 아래와 같다.

      1
      |
      2
     / \
    3   4
    |
    5
    |
    6

• S = 1 (출발점)
• D = 1 → 깊이가 1 이하인 노드는 자동으로 전단지 배포가 가능하다.
• 따라서, 깊이가 1을 초과하는 노드(깊이 2 이상)만 방문하면 된다.

D = 1인 경우, 이동해야 하는 노드를 보면 다음과 같다. → 깊이가 1보다 큰 노드 직접 방문

노드	깊이	직접 방문 여부
2	4	✅
3	3	✅
4	1	❌ (자동 배포 가능)
5	2	✅
6	1	❌ (자동 배포 가능)

따라서, 직접 방문해야 하는 노드는 2, 3, 5번이다.

즉, 이동해야 하는 간선의 개수 cnt = 3이고, 왕복 거리를 계산하면 결과는 6이 된다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 64284KB
시간 : 400ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int n, s, d, cnt;
    static ArrayList<Integer>[] list;
    static int[] depth;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 노드의 개수
        s = Integer.parseInt(st.nextToken()); // 케니소프트의 위치
        d = Integer.parseInt(st.nextToken()); // 힘

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

        int x, y;
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            list[x].add(y);
            list[y].add(x);
        }

        depth = new int[n+1];
        dfs(s, -1);

        // 왕복 간선의 갯수 == 시작점을 제외한 방문노드의 개수*2
        System.out.println(cnt*2);
    }

    private static int dfs(int start, int parent) {
        // 리프 노드를 시작으로 depth를 1씩 증가시키기
        for (int next : list[start]) {
            if (next != parent) {
                // 서브노드가 2개 이상일 경우 더 깊은 depth 값을 적용
                depth[start] = Math.max(depth[start], dfs(next, start)+1);
            }
        }

        // 노드의 거리가 d가 넘는 경우 탐색하는 노드이므로
        // 시작점은 카운트하지 않아도 됨
        if (start != s && depth[start] >= d) {
            cnt++; // 카운트
        }

        return depth[start];
    }
}

 

알고리즘 문제는 매일 풀어도 풀어도 새롭고 어렵다..

그래도 블로그 포스팅하면서 한 번 더 정리 겸 복습하니까 이해가 좀 더 잘 되는 것 같기도..😂