https://www.acmicpc.net/problem/11725

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

7
1 6
6 3
3 5
4 1
2 4
4 7

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

4
6
1
3
1
4

풀이

트리라고 해서 트리 구조를 만들어야 하나? 라고 생각할 수도 있는데, 그냥 그래프를 그려서 해결하면 된다.

주목해야 할 부분은 트리 구조의 특징이다. 트리는 그래프의 특수한 형태로 어떤 정점의 인접한 정점은 반드시 부모 노드 혹은 자식 노드라는 특징이 있다. 이를 이용하여 루트 노드에서부터 탐색을 시작하면 특정 노드의 부모 노드를 알 수 있다.

    1
  4   6
2  7    3
          5

위의 트리를 예시로 들어 설명하자면
루트 노드 1 방문
-> 1의 인접한 정점은 4와 6
-> 1이 루트 노드이므로 4와 6은 전부 자식 노드
-> 즉 4와 6의 부모 노드는 1

노드 4 방문
-> 4의 인접한 정점은 1, 2, 7
-> 이 중 1은 이미 방문했으므로 인접한 정점을 찾는 과정에서 제외(부모 노드)
-> 남은 2와 7은 자식 노드
-> 즉 2와 7의 부모 노드는 4

이러한 과정을 통해 특정 노드의 부모 노드를 알아낼 수 있다.

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BJ_11725 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // 노드 개수 입력

		// 트리 구조 표현을 위한 그래프 구현
		ArrayList<ArrayList<Integer>> tree = new ArrayList<>();
		for (int i = 0; i < n; i++)
			tree.add(new ArrayList<>());

		// 그래프 입력
		for (int i = 0; i < n - 1; i++) {
			int n1 = sc.nextInt() - 1;
			int n2 = sc.nextInt() - 1;
			tree.get(n1).add(n2);
			tree.get(n2).add(n1);
		}

		boolean[] visited = new boolean[n]; // 방문 여부 확인용 배열
		int[] parentNode = new int[n]; // 부모 노드 저장 배열

		// BFS
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		visited[0] = true;
		while (!queue.isEmpty()) {
			int v = queue.remove();
			for (int node : tree.get(v))
				if (!visited[node]) {
					visited[node] = true;
					queue.add(node);
					parentNode[node] = v; // 부모 노드 찾은 후 저장
				}
		}

		// 루트 노드를 제외한 나머지 노드의 부모 노드 출력
		for (int i = 1; i < n; i++)
			System.out.println(parentNode[i] + 1);
	}

}