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

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

11725번: 트리의 부모 찾기

 

풀이 :

1. 트리상에 연결되어 있는 정점들을 입력받을 graph 리스트 생성

2. 각 노드들의 부모노드를 저장할 parent 리스트 생성

3. 간선의 방향이 정해져 있지 않기 때문에

graph[a].append(b)

graph[b].append(a)

와 같이 입력받은 노드들을 저장해줌

4. bfs알고리즘을 통해 정점마다 들어있는 노드들을 순회하면서 parent값이 0이면(아직 parent값이 안들어간 것이므로) parent값(v)을 넣어줌

5. parent의 2번째부터 출력하면 답 (why? 2번 노드부터 부모노드를 순서대로 출력하라고 했으므로!)

 

코드 :

from collections import deque
N = int(input())

graph = [[] for _ in range(N+1)]
parent = [0] * (N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def bfs(start):
    q = deque()
    q.append(start)
    while q:
        v = q.popleft()
        for i in graph[v]:
            if parent[i] == 0:
                q.append(i)
                parent[i] = v
bfs(1)
for i in range(len(parent[2:])):
    print(parent[i+2])