📚 11725 - 트리의 부모 찾기

트리의 부모 찾기

이해

• 문제를 보면 부모노드부터 자식노드까지 전체를 연결해야한다.
• 연결할 때, 1번 노드부터 시작하여 돌리다가 아직 방문하지 않은 노드이라면 그 노드와 연결한다.
• 연결될 때 부모노드가 누구인지 저장해놓는다.
• dfs, bfs두 개 다 가능하다.

풀이

dfs

import sys
sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline())
tree = [[] for _ in range(n + 1)]
parent = [0 for _ in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)


def dfs(num):
    for i in tree[num]:
        if parent[i] == 0:
            parent[i] = num
            dfs(i)

dfs(1)

for cur_node in parent[2:]:
    print(cur_node)

bfs

import sys
from collections import deque

n = int(sys.stdin.readline())
tree = [[] for _ in range(n + 1)]
parent = [0 for _ in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)


def bfs():
    queue = deque()
    queue.append(1)

    while queue:
        node = queue.popleft()

        for alc_node in tree[node]:
            if parent[alc_node] == 0:
                parent[alc_node] = node
                queue.append(alc_node)


bfs()

for cur_node in parent[2:]:
    print(cur_node)

채점 결과
dfs는 Python으로 채점해야 맞다고 나온다.
bfs는 상관없다.