악곱 == 악성곱슬

BFS, 트리

---

이 문제는 트리(그래프) 의 간선을 주고, 각 노드의 부모를 찾으라는 문제이다. 즉, 간선을 가지고 어떻게 트리 구조를 형성한 후, 부모 노드를 찾을 것인가에 대해 고민하면 된다.

따라서 나는 인접 리스트(adjcency list)를 활용하여, 양방향 그래프로 구축하였다. 그리고 BFS를 이용하여, 루트 노드부터 아래로 한층씩 내려가며 부모 노드를 하나씩 저장하는 방식으로 구현했다. 따라서 시간복잡도는 O(N)정도 소요된다.

코드는 다음과 같다.

구현

---

import sys
from collections import deque

def bfs(n):
    parent = [0] * (n + 1)
    visited = [False] * (n + 1)
    q = deque()
    q.append(1)
    visited[1] = True
    while q:
        cur = q.popleft()
        for node in tree[cur]:
            # 이미 방문했던 상위 노드라면
            if visited[node]:
                continue
            parent[node] = cur
            visited[node] = True
            q.append(node)
    for i in range(2, n + 1):
        print(parent[i])

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    tree = [[] for _ in range(N + 1)]
    for _ in range(N - 1):   # 양방향 그래프로 트리구조를 저장
        a, b = map(int, sys.stdin.readline().rstrip().split())
        tree[a].append(b)
        tree[b].append(a)
    bfs(N)