[백준] 11725. 트리의 부모 찾기 (Python)

백준 문제 풀이 - 그래프 탐색

📰 문제

문제 확인 🏃

💡 입출력 예제

7
1 6
6 3
3 5
4 1
2 4
4 7

>> 4 >> 6 >> 1 >> 3 >> 1 >> 4

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

>> 1 >> 1 >> 2 >> 3 >> 3 >> 4 >> 4 >> 5 >> 5 >> 6 >> 6

💬 풀이

🎵 첫번째 풀이

from collections import deque
import sys


input = sys.stdin.readline
N = int(input())                        # 노드의 개수
nodes = [[] for _ in range(N+1)]        # 인접 리스트    
for _ in range(N-1):
    i, j = map(int, input().split())
    nodes[i].append(j)
    nodes[j].append(i)


def solution():
    parent = [-1] * (N+1)

    queue = deque()

    queue.append(1)
    parent[1] = 1

    while queue:
        now = queue.popleft()

        for nn in nodes[now]:
            if parent[nn] == -1:
                parent[nn] = now
                queue.append(nn)

    return parent[2:]


parent = solution()
for p in parent:
    print(p)

🎵 두번째 풀이

import sys
sys.setrecursionlimit(10**6)


input = sys.stdin.readline
N = int(input())                        # 노드의 개수
nodes = [[] for _ in range(N+1)]        # 인접 리스트    
for _ in range(N-1):
    i, j = map(int, input().split())
    nodes[i].append(j)
    nodes[j].append(i)

# 각 노드의 부모 테이블
parent = [-1] * (N+1)
parent[1] = 1


def solution(start):
    for n in nodes[start]:
        if parent[n] == -1:
            parent[n] = start
            solution(n)


solution(1)
for p in parent[2:]:
    print(p)

✒️ 생각