(Python) - BOJ(11725번) : 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

---

• 문제 : 

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

 

 

 

---

• 풀이 :

트리의 루트부터 BFS 또는 DFS로 순회한다. 1인 루트부터 순회하는것이 보장되어 있으므로 현재 탐색중인 노드로부터 방문하지 않은 어떤 노드와 연결관계가 있을 경우 현재 탐색중인 노드가 방문하지 않은 노드의 부모노드가 된다. 

 

 

 

---

• 소스코드 : 

from collections import deque

N = int(input())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
for _ in range(N-1):
    A, B = map(int,input().split())
    graph[A].append(B)
    graph[B].append(A)
queue = deque()
queue.append(1)
visited[1] = 1
while queue:
    node = queue.popleft()
    for i in graph[node]:
        if visited[i] == 0:
            queue.append(i)
            visited[i] = node
for i in visited[2:]:
    print(i)