백준 11725번 : 트리의 부모 찾기 (unchecked 문제 포함)
이번 문제는 루트 없는 트리가 주어지고 해당 트리의 루트를 1이라고 가정했을 때, 각 노드의 부모 노드를 구하는 문제이다.
노드의 개수 N과 N-1개의 연결된 두 정점이 입력된다.
우선 각각 트리의 구성과 탐색을 위한 방문 여부 등 필요한 전역 변수를 선언한다.
1
2
3
4
public class Main {
static ArrayList<Integer>[] tree;
static int[] parent;
static boolean[] visited;
tree는 각 노드와 그 노드에 연결된 노드들의 정보를 저장하는 배열이고,
parent는 각 노드의 부모 노드를 저장하는 배열이다.
마지막으로 visited는 탐색에 필요한 방문 여부 체크를 위한 배열이다.
이제 메인 함수에서 트리를 구현하고 탐색을 실행할 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
StringTokenizer st;
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
parent = new int[n + 1];
visited = new boolean[n + 1];
dfs(1, 0);
// bfs(1);
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i++) {
sb.append(parent[i]).append('\n');
}
System.out.println(sb);
}
앞서서 멤버 변수로 tree의 타입을 ArrayList 배열로 지정했는데, 노드 간의 관계를 타나내기 위해서이다.
현재 입력 받고 활용해야할 데이터는 트리 구조로 되어 있어, 각 노드가 여러 개의 자식 노드를 가질 수 있다.
이런 경우에 각 노드와 연결된 노드들의 관계를 표현하기 위해 각 노드를 인덱스로, 연결된 노드들의 리스트를 값으로 가지는 데이터 구조가 필요하다.
그래서 현재와 같이 각 인덱스가 노드 번호를 나타내고, 그 인덱스에 해당하는 ArrayList에는 연결된 노드들의 번호가 저장되는 ArrayList
유의해야할 점은 위와 같은 이유로 선언된 tree 변수에
1
tree = new ArrayList[n + 1];
ArrayList[] 타입의 배열을 할당하고 있는데, 여기서 ArrayList[]는 raw 타입의 배열이고, 다시 말해 제네릭 타입의 매개변수가 지정되지 않은 ArrayList를 의미한다.
자바에서는 제네릭 배열 생성을 허용하지 않기 때문에 unchecked 경고가 발생한다.
배열은 공변성(covariance)을 가지고, 하위 타입의 배열을 상위 타입의 배열에 할당할 수 있다는 것을 의미한다.
반면, 제네릭은 불공변성(invariance)을 가지고, 하위 타입의 제네릭을 상위 타입의 제네릭에 할당할 수 없다는 것을 의미한다.
즉, 제네릭 배열을 만들면 두 가지 속성이 충돌하게 되어 예상치 못한 결과가 발생할 수 있다.
현재는 타입을 조금 삐끗하면 ClassCastException이 발생할 수 있는 상황인 것이다.
이를 해결하기 위해 ArrayList<ArrayList
다시 돌아와 그 다음 반복문에서는 각 노드의 연결을 표현하기 위해 x와 y로 나누어 tree에 저장한다.
이 때, 서로 교차해서 삽입하는데, 이는 서로 연결되어 있음을 의미한다.
한 가지 주의해야할 점은 모든 배열이 n + 1 크기로 초기화되는데, tree의 인덱스 = 노드 번호이기 때문에 첫 인덱스인 0을 제외해야해서 한 칸씩 뒤로 미루기 위한 작업이다.
마찬가지로 tree의 각 배열 내 ArrayList를 초기화 할때 0부터 시작하되, n까지 진행되는 모습을 보면 알 수 있다.
이후, 부모 노드를 저장할 parent와 탐색 시 방문 여부를 체크할 visited 배열을 초기화한다.
이 과정이 끝나면 DFS 혹은 BFS로 탐색을 시작한다.
1. DFS
1
2
3
4
5
6
7
8
9
10
public static void dfs(int node, int x) {
visited[node] = true;
parent[node] = x;
for (int child : tree[node]) {
if (!visited[child]) {
dfs(child, node);
}
}
}
먼저 구현한 DFS 탐색이다.
매개 변수인 node는 현재 노드, x는 부모 노드를 의미한다.
문제에서 주어졌듯이 현재 노드는 1부터 시작해야하며, 1의 부모 노드는 없으므로 0으로 진행한다.
반복문에서는 tree의 현재 노드와 연결된 노드들을 추출해 child 변수에 할당하고 각 자식 노드를 방문하지 않았다면 재귀가 실행된다.
재귀를 반복하게 되면 parent 배열에는 1을 제외한 각 노드들의 부모노드가 저장된다.
2. BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void bfs(int node) {
visited[node] = true;
Queue<Integer> q = new LinkedList<>();
q.offer(node);
while (!q.isEmpty()) {
int cur = q.poll();
for (int child : tree[cur]) {
if (!visited[child]) {
q.offer(child);
visited[child] = true;
parent[child] = cur;
}
}
}
}
이번엔 BFS 탐색이다.
마찬가지로 시작인 1번 노드를 방문 여부 true로 변경하고 큐를 생성해 현재 노드를 큐에 삽입한다.
정석대로 while 문을 실행하고 cur 변수에 현재 노드를 할당한다.
반복문을 실행시켜 child 변수에 tree의 현재 노드와 연결된 노드들을 추출해 할당한다.
큐에 현재 노드를 다시 삽입하고, 현재 위치 방문 여부를 true 체크했으며, 현재 노드의 이전 노드가 부모 노드이기 때문에 parent 배열의 각 인덱스에 삽입한다.
이 두 가지 탐색을 실행하면 parent 노드에는 각 인덱스는 자식 노드, 값은 부모 노드가 저장된다.
이를
1
2
3
4
5
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i++) {
sb.append(parent[i]).append('\n');
}
System.out.println(sb);
반복문을 실행시켜 0을 패스하고, 시작인 1을 제외하고 2번 인덱스부터 n번 까지 parent의 값들을 출력하면 정답이 된다.
참고로 빠른 출력을 위해 sb를 사용했다.
전체 소스코드는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static ArrayList<Integer>[] tree;
static int[] parent;
static boolean[] visited;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
StringTokenizer st;
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
tree[x].add(y);
tree[y].add(x);
}
parent = new int[n + 1];
visited = new boolean[n + 1];
dfs(1, 0);
// bfs(1);
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= n; i++) {
sb.append(parent[i]).append('\n');
}
System.out.println(sb);
}
public static void dfs(int node, int x) {
visited[node] = true;
parent[node] = x;
for (int child : tree[node]) {
if (!visited[child]) {
dfs(child, node);
}
}
}
public static void bfs(int node) {
visited[node] = true;
Queue<Integer> q = new LinkedList<>();
q.offer(node);
while (!q.isEmpty()) {
int cur = q.poll();
for (int child : tree[cur]) {
if (!visited[child]) {
q.offer(child);
visited[child] = true;
parent[child] = cur;
}
}
}
}
}
위에서부터 아래로 DFS, BFS 탐색 결과다.
각 하위 노드들의 부모노드를 구하는 문제이기 때문에 너비를 먼저 둘러보는 BFS가 비교적 빠르게 탐색할 수 있다.
노드 관련 문제는 많이 풀어보지 않아서 좀 더 상세하게 적었다.
그래프는 어느정도 파악했는데 트리는 여전히 헷갈린다.
아직 문제를 많이 접해보질 못해서인 것 같아, 가능하면 더 만나보고싶다.