[백준 11725번] 트리의 부모 찾기

mokomoko·2022년 1월 12일

1. 문제

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

제한 사항

시간 : 1 초
메모리 : 256 MB

입력

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

출력

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

- 키워드

자식 노드가 2개라고 명시되어 있지 않다. 즉, 이진트리가 아니다.

N이 100,000까지 있을 수 있다. 메모리 사용에 주의할 필요가 있다.

2. 풀이

트리의 경우 가장 보편적으로 사용되는 이진트리를 바로 떠올리겠지만,

해당 문제에서는 자식노드가 최대 2개라고 명시되어 있지 않기 때문에

이진트리를 활용하기에는 어려움이 있어보인다.

나는 Python의 dict 자료형을 활용해보기로 했다.

예제 테스트케이스로 다음을 입력했다.

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

해당 테스트케이스를 tree로 그리면 다음과 같다.

여기서 dict를 활용해 그래프 형식으로 저장한다.

저장하면 다음과 같다.

이 상태로, 1부터 큐를 사용해 차례대로 탐색한다.

1과 연결되어 있는 노드는 2,3,4 이므로 2,3,4를 차례대로 방문한다.

2,3,4는 parent가 갱신되어 있지 않으므로, 1의 자식노드이다.

2,3,4의 parent를 갱신해주고 큐에 삽입한다.

다음으로 2를 탐색한다.

여기서 1,6,7,8을 만나게 되는데 1은 root이므로 제외하고,

6,7,8은 parent에 갱신되어 있지 않으므로 자식노드이므로, 갱신해주고 큐에 삽입한다.

다음으로 3을 탐색한다.

여기서 1,5를 만나고, 1은 root이므로 제외하고 5를 갱신하고 큐에 삽입한다.

다음 4를 탐색한다.

1을 만나고, 1은 root이므로 제외한다. 자식노드가 없으므로 큐에서 제외되기만 한다.

다음 6을 탐색한다.

2를 만나고 2는 parent가 갱신되어 있는 상태기 때문에 부모노드이다.

그러므로 갱신되는 것은 없고, 큐에서 제외되기만 한다.

다른 노드 역시 같은 과정을 거친다.

큐가 비게되면 탐색을 종료하고 결과를 출력한다.

이 방식을 보면, 트리 순회라고 하기보단 BFS에 가깝다.

3. 소스코드

import sys
from collections import deque
input = sys.stdin.readline

def solution(N,tree):
	q = deque([1])
	parent = [0] * (N+1)
	while q:
		now = q.popleft()
		for i in tree[now]:
			if parent[i] == 0 and i != 1:
				parent[i] = now
				q.append(i)
	for i in range(2,N+1):
		print(parent[i])

if __name__ == "__main__":
	N = int(input())
	tree = dict()
	for i in range(1,N+1):
		tree[i] = []
	for _ in range(N-1):
		n1,n2 = map(int,input().split())
		tree[n1].append(n2)
		tree[n2].append(n1)
	solution(N,tree)