[99클럽 코테 스터디] 31일차 TIL DFS/BFS

 

 

오늘의 문제는 백준

 

6188. Clear Cold Water

 

 

문제

 

 

 

문제 설명 

농장에서 출발하여 N개의 파이프가 트리 구조로 연결된 시스템에서, 각 파이프의 끝점까지의 거리를 계산하여 가장 차가운 물이 흐르는 곳을 찾는 문제입니다. 각 파이프의 길이는 1이며, 입력으로 주어진 파이프 연결 정보를 바탕으로 헛간에서 각 파이프 끝점까지의 최단 거리를 출력해야 합니다.

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 52분이 걸렸습니다.

 

 

 

문제 접근 방식

먼저 트리를 인접 리스트로 표현한 다음 각 노드에서 연결된 노드를 탐색하며 거리를 계산했습니다. 시작점인 파이프 1부터 BFS를 수행하여 각 노드까지의 거리를 구하고, 이 거리를 배열에 저장한 후 모든 파이프의 끝점까지의 거리를 출력하는 방식으로 문제를 풀었습니다. 

 

 

 

문제 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int C = sc.nextInt();  

        List<List<Integer>> tree = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            tree.add(new ArrayList<>());
        }

        for (int i = 0; i < C; i++) {
            int E = sc.nextInt();
            int B1 = sc.nextInt();
            int B2 = sc.nextInt();

            tree.get(E).add(B1);
            tree.get(E).add(B2);
            tree.get(B1).add(E);
            tree.get(B2).add(E);
        }

        int[] distances = new int[N + 1];
        Arrays.fill(distances, -1); 
        distances[1] = 1;  

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

        while (!queue.isEmpty()) {
            int current = queue.poll();

            for (int neighbor : tree.get(current)) {
                if (distances[neighbor] == -1) {  
                    distances[neighbor] = distances[current] + 1;
                    queue.add(neighbor);
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            System.out.println(distances[i]);
        }

        sc.close();
    }
}

 

 

 

 

 

 

 

 

 

 

이렇게 오늘 31일차 TIL을 작성해 보았습니다.