[백준] 트리의 부모 찾기

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

분류:: bfs

 

1. 문제 이해 및 해결과정

- 가장 가까운 노드 찾으면 된다

 

 

2. 풀이방법

  1. [ python ] bfs

#트리의 부모 찾기
#https://www.acmicpc.net/problem/11725
import sys
from collections import deque
sys.stdin = open("input.txt","r")
n=int(input())
tree=[[] for _ in range(n+1)]
visited=[False for _ in range(n+1)]
res=[0]*(n+1)

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


def bfs():
    q=deque([1]) #1이 루트노드
    while q:
        parent=q.popleft()
        # print(parent,q)
        for x in tree[parent]:
            if not visited[x]: #처음 방문한 것만 부모를 찾으면 됨
                res[x]=parent
                visited[x] = True
                q.append(x) #다음 탐색할 노드 넣기


bfs()
print('\n'.join(map(str,res[2:])))

 

3. 오답원인

 

4. 알게된 점