오늘의 주제는 깊이/너비 우선 탐색(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]);
}
}
}