알고리즘 - Python / 백준 - 11725번 : 트리의 부모 찾기

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기

 

---

풀이

• 트리의 간선을 입력받고 해당 노드에 대해서 부모를 찾는 문제이다.
• 간단한 트리 탐색 문제 이므로 , bfs를 통해서 해결 하였다.
• bfs를 구현시 , 큐에 자식노드를 넣는 과정에서 해당 부모 노드의 번호를 함께 넣어 쌍으로 입력하였고 , 나중에 pop 할때 정답 배열에 해당 부모 노드를 입력 하였다.

 

import sys
e = int(sys.stdin.readline())
s = [[] for _ in range(e + 1)]
for i in range(e-1):
    u, v = map(int, sys.stdin.readline().split())
    s[u].append(v)
    s[v].append(u)
def bfs():
    global s
    ans = [0]*(len(s)+1)
    stack = [[1,0]]
    visited = [0]*(len(s)+1)
    while stack:
        n = stack.pop(0)
        if visited[n[0]] == 0:
            visited[n[0]] = 1
            ans[n[0]] = n[1]
            for i in s[n[0]]:
                stack.append([i,n[0]])
    for i in range(2,e+1):
        print(ans[i])
bfs()

---