11725번: 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
www.acmicpc.net
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
예제 입력 1
7
1 6
6 3
3 5
4 1
2 4
4 7
예제 출력 1
4
6
1
3
1
4
예제 입력 2
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 1
0 6
11
6 12
예제 출력 2
1
1
2
3
3
4
4
5
5
6
6
풀이 .
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] map = null;
static int[] parent = null;
static boolean[] check = null;
public static void dfs(int node) {
for(int next : map[node]) {
if(!check[next]) {
check[next] = true;
parent[next] = node;
dfs(next);
}
}
}
public static void bfs(int root) {
Queue<Integer> que = new ArrayDeque<>();
que.add(root);
check[root] = true;
while(!que.isEmpty()) {
int now = que.poll();
for(int next : map[now]) {
if(!check[next]) {
check[next] = true;
parent[next] = now;
que.add(next);
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int n = Integer.parseInt(br.readLine());
map = new ArrayList[n + 1];
parent = new int[n + 1];
check = new boolean[n + 1];
for(int i = 1; i <= n; i++) {
map[i] = new ArrayList<>();
}
for(int i = 0; i < n-1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
map[u].add(v);
map[v].add(u);
}
// dfs(1); check[1] = true;
bfs(1);
for(int i = 2; i <= n; i++) {
sb.append(parent[i] + "\n");
}
bw.write(sb.toString());
br.close();
bw.flush();
bw.close();
}
}
DFS, BFS 를 사용해 트리의 탐색을 할 수 있다.
(트리도 그래프이다. 사이클이 없으며 반드시 모든 노드가 연결된 그래프.)
int[] parent를 사용해 탐색을 진행하며 각 노드의 부모노드를 알아낼 수 있다.
(루트를 제외한 모든 노드는 하나의 부모만을 갖기 때문에 next로 넘어가기 전 노드인 now가 next의 노드가 된다.)
'알고리즘 문제 > 백준 온라인 저지' 카테고리의 다른 글
[BOJ] 1967 - 트리의 지름(1967) JAVA (0) | 2021.01.20 |
---|---|
[BOJ] 1167 - 트리의 지름(1167) JAVA (0) | 2021.01.20 |
[BOJ] 1991 - 트리 순회 JAVA (0) | 2021.01.20 |
[BOJ] 2146 - 다리 만들기 JAVA (0) | 2021.01.20 |
[BOJ] 2178 - 미로 탐색 JAVA (0) | 2021.01.19 |