2022.05.09 [백준] (python 파이썬) 트리의 부모 찾기

 

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

11725번: 트리의 부모 찾기

 

---

풀이

이 문제를 해결하기 위해 BFS를 이용했다. 이유는 1을 루트 노드로 정했을 때, 1을 기준으로 각 자식노드로 내려가며 vis배열에 부모노드를 저장하기 위해서 이다.

 

우선 graph배열에 각 노드와 연결된 노드들을 저장했다.

그리고 각 노드에 대한 방문여부를 확인하고 각 노드의 부모 노드를 저장하기 위한 vis배열을 -1로 초기화하였다.

이 후, 루트 노드인 1을 bfs배열에 넣어 vis[1]을 0으로 선언 후 while문으로 각 노드의 자식노드를 확인했다.

자식노드가 방문하지 않은 노드면 vis[자식노드]에 부모노드의 번호를 저장했다.

 

from collections import deque
 
n=int(input())
 
graph=[[] for _ in range(n+1)]
 
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
 
vis=[-1]*(n+1)
 
def bfs(a):
    deq=deque()
    deq.append(a)
    vis[a]=0
    while deq:
        node=deq.popleft()
        for i in graph[node]:
            if vis[i] == -1:
                deq.append(i)
                vis[i]=node
 
bfs(1)
 
for i in range(2,n+1):
    print(vis[i])