[BOJ] 백준 19542 : 전단지 돌리기 (java)

🧪 19542 전단지 돌리기 

---

난이도 : 🌟 골드 3
유형 : 그래프 탐색 (DFS)

19542번: 전단지 돌리기

 

📝 문제

---

 

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

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

 

입력

 

 

출력

 

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

 

🚧  주의할 점

---

1. 되돌아가지 않도록 visited를 통해 방문 처리를 해줘야 한다.

 

🧐 핵심 로직

---

1. 리프노드 중 가장 거리가 큰 값이 들어갈 변수 max를 정의한다.
2. 간선을 탐색하며 리프노드부터의 거리를 역으로 return 하며 찾는다.
3. return 값이 d보다 크거나 같은 노드만 ans 값을 올려준다.
4. 결과값은 정답에서 루트 노드를 제외한 값 * 2

 

💻 최종 코드 (548 ms)

---

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

public class Main {

    static int n, s, d, ans;
    static List<List<Integer>> edgeMap;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        ans = 0;
        edgeMap = new ArrayList<>();
        visited = new boolean[n + 1];

        for (int i = 0; i <= n; i++) {
            edgeMap.add(new ArrayList<>());
        }

        for (int i = 0; i < n-1; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            edgeMap.get(v1).add(v2);
            edgeMap.get(v2).add(v1);
        }

        dfs(s);

        System.out.println(Math.max(0, (ans - 1) * 2));

        br.close();
    }

    private static int dfs(int v) {

        int max = 0;
        visited[v] = true;

        for (int next : edgeMap.get(v)) {
            if (visited[next]) continue;
            visited[next] = true;

            max = Math.max(max, dfs(next));
        }

        if (max >= d) {
            ans++;
        }

        return max + 1;
    }
}