[파이썬] 백준 11725 : 트리의 부모 찾기

[파이썬] 백준 11725 : 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

실버 2

그래프, BFS

---

접근

이 문제는 그래프 이론을 이해한 사람이면 누구나 바로 풀어낼 수 있는 문제라고 생각한다. 실버 3으로 강등해도 괜찮은 것 같다.

방문 처리를 할때 부모의 노드 번호를 새겨주고 2~N까지의 방문 처리 값을 출력하면 끝이다.

 

코드(BFS)

import sys; input= sys.stdin.readline
from collections import deque

def bfs(node):
    queue = deque([node])
    visited[node] = 1
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = v  # 방문처리를 하되, 부모의 노드 번호를 새겨준다.

N = int(input())
graph = [[] for _ in range(N+1)]
visited = [0] * (N+1)
for _ in range(N-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
bfs(1)
print("\n".join(str(visited[i]) for i in range(2, N+1)))