[자바] 백준 19542 - 전단지 돌리기 (java)

 문제 : boj19542

---

 

필요 알고리즘 개념

• 깊이 우선 탐색 (dfs), 트리
  
  • 트리를 dfs로 적절한 방식으로 탐색하는 문제이다. 기본적으로 dfs에 대한 이해가 필요하다. 트리에 대한 이해도 있으면 생각하기 더 좋다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  요즘 바빠서 브론즈문제로 스트릭만 유지하고 있었다. 현재 405일이라 깨기는 너무 아깝다 ㅋㅋ

 

   이제 좀 바쁜게 풀려서 다시 문제들좀 풀어보려니 오랜만이라 그런지 감이 안돌아와서 좀 버벅였다. 나름 자신있는 그래프 탐색류의 문제인데도 아예 처음보는 유형의 문제라 재활(?)하기에 딱 좋았다.

 

---

 

  이 문제에서 구해야 하는건 각 노드에서 D이하의 모든 노드에 전단지를 돌릴 수 있을 때, 모든 노드에 전단지를 돌리기 위해 'S에서 시작해 어느 노드까지 가면 되는지' 라고 볼 수 있다. 주어진 S를 루트로 생각할 때 결국 가장 멀리 있는 곳들은 리프노드들이 된다. 따라서 모든 리프노드들에 빠짐없이 도달하기 위해 '어느 노드까지 가면 되는지'를 생각해보면 된다('트리' 구조라고 했으므로 사이클 등은 생각하지 않아도 된다.)

 

1. 아래와 같은 구조를 생각해보자. D=N일 경우, 당연히 S에서 모든 위치에 도달 가능하므로 안움직여도 된다. (답은 0)

 

 

2. D=0일 경우라면 모든 리프노드까지 모두 가봐야 한다. 노란색으로 칠한게 가야하는 노드들이다. 답은 가야하는 노드들의 개수 x 2 이다(S로 다시 되돌아와야 하므로). 아래와 같은 경우라면 답은 18이 된다.

 

 

3. D=1일 경우를 보자. 여기부터가 중요하다. 모든 노드에서 D 이하인 모든 노드에 전단지를 돌릴 수 있고, 모든 리프노드에 전단지를 돌려야 한다. 따라서 S에서 출발해 각 노드에서 도달할 수 있는 리프노드 중 거리가 D보다 크거나 같은 모든 노드를 방문해야 한다. 그림으로 표현해보면 다음과 같다. 빨간 글자가 해당 노드에서 갈 수 있는 리프노드 중 가장 거리가 먼 리프노드의 거리이다. 빨간 글자가 1인 곳까지(D=1이므로) 방문했다. 답은 10이 된다.

 

4. D=2인 경우를 보자. 마찬가지로 빨간글자가 2인 곳까지 갔음을 알 수 있다. 답은 6이 된다.

 

5. D=3은 답이 2가 된다. S노드에서 4번 리프노드까지 전단지를 돌릴 수 있고, 2번 노드에서 나머지 모든 노드로 전단지를 돌릴 수 있다.

 

6. 4<=D<=N 에 대해서는 답이 0이 된다. S에서 모든 위치에 전단지를 돌릴 수 있다.

 

---

 

  위의 설명으로 답을 어떻게 찾는지 이해했다면, S에서 시작해 DFS를 진행하면서 모든 노드에서 리프노드까지의 최대 거리를 알면 답을 구할 수 있음을 예상할 수 있다. 풀이를 이해한 이후는 구현력(?)의 영역이므로, 코드에 주석을 다는것으로 설명을 대신한다.

private int dfs(int cur) {
    int max = 0;	// cur번 노드에서 도달 가능한 리프노드 중 가장 거리가 큰 값
    for (int next : edges[cur]) {	// 문제에서 제시된 간선을 탐색
        if (v[next]) continue;	// 트리이므로 사이클은 없으니 이건 S에서 출발해 cur에 도착했는데 다시 뒤돌아가지 않기 위한 방문체크이다.
        v[next] = true;
        max = Math.max(max, dfs(next));	// 리프노드부터의 거리를 역으로 return하면서 내려와 알 수 있다.
    }
    if (max>=d) ans++;	// 그림으로 설명했듯이 d보다 크거나 같은 모든 노드에 방문해야 한다. 그림에서 노란색으로 된 부분이 ans++에 해당한다.
    return max+1;	// 리프노드까지의 거리에서 cur번 노드가 추가되므로 +1로 리턴한다.
}

 

---

 

코드 : github

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

public class Main {
    ArrayList<Integer>[] edges;
    int d;
    boolean[] v;
    int ans = 0;

    private int dfs(int cur) {
        int max = 0;
        for (int next : edges[cur]) {
            if (v[next]) continue;
            v[next] = true;
            max = Math.max(max, dfs(next));
        }
        if (max>=d) ans++;
        return max+1;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        edges = new ArrayList[n+1];
        v = new boolean[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            edges[x].add(y);
            edges[y].add(x);
        }
        v[s] = true;
        dfs(s);
        System.out.println(Math.max(0, (ans-1)*2));
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}