99클럽 코테 스터디 31일차

ㅎㅇ·2024년 8월 22일
0

항해99 TIL

목록 보기
25/33

❓Clear Cold Water

오늘의 주제는 깊이/너비 우선 탐색(DFS/BFS)

✏️ 풀이
트리 구조에서 각 파이프까지의 거리를 계산하는 문제

풀이1
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>> graph = new ArrayList<>();
    for (int i = 0; i <= n; i++) {
        graph.add(new ArrayList<>());
    }

    for (int i = 0; i < c; i++) {
        int point = sc.nextInt(); // 연결점
        int pipe1 = sc.nextInt(); // 첫번째 파이프
        int pipe2 = sc.nextInt(); // 두번째 파이프
        
        graph.get(point).add(pipe1);
        graph.get(point).add(pipe2);
        graph.get(pipe1).add(point);
        graph.get(pipe2).add(point);
    }

    int[] distances = new int[n + 1];
    Arrays.fill(distances, -1); // 방문하지 않은 파이프 -1로 초기화

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

    while (!queue.isEmpty()) {
        int current = queue.poll();
        int currentDistance = distances[current];

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

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

}

profile
안녕하세요

0개의 댓글