[Silver II] 트리의 부모 찾기 - 11725
성능 요약
메모리: 99136 KB, 시간: 2072 ms
분류
그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
제출 일자
2024년 1월 11일 23:22:34
문제 설명
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Main {
static int n;
static ArrayList<Integer>[] list;
static int[] parent;
public static void main(String args[]) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 노드의 개수를 저장
n = Integer.parseInt(br.readLine());
// 인접 리스트를 만들어준다.
list = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
list[i] = new ArrayList<>();
}
// 각 부모를 저장하기 위한 배열
parent = new int[n+1];
for (int i = 0; i < n - 1; i++) {
String[] nums = br.readLine().split(" ");
int a = Integer.parseInt(nums[0]);
int b = Integer.parseInt(nums[1]);
// 연결시켜준다. 방향을 모르니까 양방향으로 저장
list[a].add(b);
list[b].add(a);
}
// dfs로 부모 배열을 채워줌
dfs(1);
for (int i = 2; i <= n; i++) {
System.out.println(parent[i]);
}
}
private static void dfs(int index) {
// 1로는 갈 일 없으므로 2부터 시작하여 부모노드인 index와 연결된 노드를 재귀호출하여 채워준다.
for (int nextNode : list[index]) {
if(parent[nextNode] == 0){
parent[nextNode] = index;
dfs(nextNode);
}
}
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 1991번 : 트리 순회 Silver1(실버1) - JAVA[자바] (1) | 2024.01.14 |
---|---|
[백준] 17829번 : 222-풀링 Silver2(실버2) - JAVA[자바] (0) | 2024.01.12 |
[백준] 18111번 : 마인크래프트 Silver2(실버2) - JAVA[자바] (0) | 2023.12.15 |
[백준] 1676번 : 팩토리얼 0의 개수 Silver5(실버5) - JAVA[자바] (0) | 2023.12.13 |
[백준] 2659번 : 십자카드 문제 Silver3(실버3) - JAVA[자바] (0) | 2023.12.13 |