문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
풀이
루트가 없는 트리가 있고 특정 노드를 루트로 정한다는 건, 문제만 읽어서는 머리속에서 잘 그려지지 않을 수 있다.
아래와 같이 예제 1을 루트를 바꿔서 여러가지 트리를 만들어보자
노드들이 끈으로 연결되어있다고 가정하면, 루트를 들어서 축 늘여뜨린다 생각하면 여러가지 트리의 형태가 생길 수 있음을 알 수 있다.
다시 문제로 돌아와서, 우리는 두 정점들의 연결 정보를 바탕으로 트리를 그려야 하는 상태이다.
위의 그림들에서 알 수 있듯 두 정점의 연결 정보는 방향성이 없다. 그래프 이론에서는 그래프를 표현할 때 인접 리스트를 이용한다.
한 꼭지점에 연결된 꼭지점들을 하나의 연결 리스트로 표현한다.
자바에서는 리스트 배열 또는 리스트의 리스트로 이를 표현한다.
필자는 풀이에서 리스트 배열로 풀이 하였다.
첫 줄에서 주어진 노드의 개수 + 1 크기의 인접리스트를 만든다. 1-based 로 설정하여 좀 더 직관적으로 풀기 위함이라 이 크기는 본인의 취향에 따라 0-based로 만들어도 된다.
그래프 문제들에서 최단 거리를 구하기 위해서 BFS를 사용하는 것을 많이 볼 수 있는데, 트리에서는 루트로 부터의 거리를 level로 표현하고, 같은 level에 대한 처리를 할 때 BFS가 적합하다 생각했다.
BFS를 위한 Queue를 하나 만들고, 문제에서 주어진 대로 1을 넣고 방문 처리를 해준다.
중복처리를 방지할 수 있기에 방문처리를 하는데, 사실 트리에서는 사이클이 없으므로 굳이 해주지 않아도 된다. 물론 방문처리를 해주면 성능상의 이점을 갖게 된다. 빅오 표기법으로 표현되는 만큼은 아니지만..
이후에는 풀이 코드에 주석으로 풀이 하겠다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 각 노드의 부모 노드를 저장하는 배열
int[] parent = new int[n + 1];
// 연결 리스트 배열
ArrayList<Integer>[] adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
adj[i] = new ArrayList<>();
}
// 방문 체크 배열
boolean[] visited = new boolean[n + 1];
StringTokenizer st;
for (int i = 1; i < n; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
adj[a].add(b);
adj[b].add(a);
}
// BFS를 위한 큐
Queue<Integer> queue = new LinkedList<>();
// 루트 노드인 1을 큐에 넣고 방문 처리
queue.add(1);
visited[1] = true;
// BFS
while (!queue.isEmpty()) {
int cur = queue.poll();
// 현재 노드에 연결된 다음 노드들을 탐색
for (int next : adj[cur]) {
// 방문했던 노드라면 건너뛴다
if (visited[next]) {
continue;
}
// 다음 노드를 방문 처리하고 큐에 넣는다.
visited[next] = true;
queue.add(next);
// 다음 노드의 부모가 현재 노드임을 저장한다.
parent[next] = cur;
}
}
// 부모 노드를 출력한다.
for (int i = 2; i <= n; i++) {
System.out.println(parent[i]);
}
}
}