[백준] 11725 : 트리의 부모 찾기 - Python

트리의 부모 찾기

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

입력

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

출력

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

import sys
sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10**6)
from collections import deque

n = int(input())
g = [[] for _ in range(n+1)]

for _ in range(n-1):
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

#각 노드의 부모 노드 번호를 출력
parent = [0] * (n+1)
ch = [0] * (n+1)

def BFS(v):
    ch[v] = 1 
    dq = deque()
    dq.append(v)
    while dq:
        x = dq.popleft()
        for node in g[x]:
            if ch[node] == 0:
                parent[node] = x
                ch[node] = 1
                dq.append(node)

BFS(1)
for i in range(2,n+1):
    print(parent[i])        
        

코멘트

이 문제는 무방향 그래프로 인접 노드들만 주어졌다. 그리고 1번이 루트노드라고 명시했기 때문에 1번부터 방문하면서 부모노드를 찾아야했다. 그리고 순서가 있기 때문에(1번부터) 방문한 노드는 재방문하면 안되므로 중복 체크를 해주면서 부모노드를 넣어주면 됐어.

• DFS/BFS 모두 풀 수 있다.