99클럽 코테 스터디 31일차 TIL | Clear Cold Water

🖥️ 문제

The steamy, sweltering summers of Wisconsin's dairy district stimulate the cows to slake their thirst. Farmer John pipes clear cold water into a set of N (3 <= N <= 99999; N odd) branching pipes conveniently numbered 1..N from a pump located at the barn. As the water flows through the pipes, the summer heat warms it. Bessie wants to find the coldest water so she can enjoy the weather more than any other cow.

She has mapped the entire set of branching pipes and noted that they form a tree with its root at the farm and furthermore that every branch point has exactly two pipes exiting from it. Surprisingly, every pipe is exactly one unit in length; of course, all N pipes connect up in one way or another to the pipe-tree.

Given the map of all the pipe connections, make a list of the distance from the barn for every branching point and endpoint. Bessie will use the list to find the very coldest water.

The endpoint of a pipe, which might enter a branching point or might be a spigot, is named by the pipe's number. The map contains C (1 <= C <= N) connections, each of which specifies three integers: the endpoint E_i (1 <= E_i <= N) of a pipe and two branching pipes B1_i and B2_i (2 <= B1_i <= N; 2 <= B2_i <= N). Pipe number 1 connects to the barn; the distance from its endpoint to the barn is 1.

📝 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        // 인접 리스트 초기화
        List<Integer>[] graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 트리 구성
        for (int i = 0; i < C; i++) {
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            graph[node].add(x);
            graph[node].add(y);
        }

        // 거리 배열 및 BFS 초기화
        int[] dis = new int[N + 1];
        Arrays.fill(dis, -1); // 초기값을 -1로 설정 (방문하지 않은 상태)
        dis[1] = 1; // 농장(1번 노드)까지의 거리는 1

        Deque<Integer> queue = new LinkedList<>();
        queue.add(1);

        // BFS 탐색
        while (!queue.isEmpty()) {
            int v = queue.poll();
            int currentDis = dis[v];

            for (int neighbor : graph[v]) {
                if (dis[neighbor] == -1) { // 아직 방문하지 않은 경우
                    queue.add(neighbor);
                    dis[neighbor] = currentDis + 1;
                }
            }
        }

        // 결과 출력
        for (int i = 1; i <= N; i++) {
            bw.write(dis[i] + " ");
        }
        bw.newLine();
        bw.flush();
    }
}

문제의 핵심은 각 노드까지의 최단 거리를 계산하는 것이다.
그렇기 때문에 먼저 트리의 노드 수 N과 연결 수 C를 읽고, 각 노드의 연결 정보를 기반으로 인접 리스트를 초기화했다. 이후, dis 배열을 사용하여 각 노드까지의 거리를 저장하고, BFS를 통해 거리를 계산했다.
또한 큐를 사용하여 현재 노드의 모든 이웃을 탐색하고, 이웃 노드의 거리를 현재 노드의 거리 + 1로 설정한다. 이후 최단 거리를 탐색하여 반환하는 계산.

🤔 고찰

BFS (Breadth-First Search)를 사용한 이유?
DFS (Depth-First Search)는 깊이 우선으로 탐색하므로 최단 경로를 보장하지 않으며, 거리 계산이 복잡해질 수 있다!

DFS는 그럼 언제?
모든 조합을 찾거나 메모리 사용을 줄이고 싶을 때!