백준 11725번. 트리의 부모 찾기 (Python / 파이썬)

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

문제 풀이

트리의 부모 찾기 문제는 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를

구하는 문제입니다.

 

트리의 루트가 1이므로 1부터 탐색을 진행하면 됩니다.

1부터 해당 노드와 연결된 노드들을 확인하고

만약 아직 부모노드가 정해지지 않았다면 해당 노드를 부모로 정해주면 됩니다.

 

DFS / BFS 알고리즘을 이용하여 문제를 해결해보았습니다.

---

My Code 1 - DFS 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def dfs(now):
    for i in graph[now]:  # 해당 노드와 연결된 노드 확인
        if parent[i] == 0: # 만약 아직 부모 노드가 없으면
            parent[i] = now # 해당 노드를 부모로 정해줌
            dfs(i)          # 연결된 노드로 재귀함수 수행

n = int(input()) # 노드의 개수

graph = [[] for _ in range(n + 1)] # 그래프
for _ in range(n - 1):
    a, b = map(int,input().split()) # 연결된 두 노드의 번호
    # 양방향으로 노드 연결
    graph[a].append(b)
    graph[b].append(a)

parent = [0] * (n + 1) # 부모 노드를 저장할 list

dfs(1) # 1부터 탐색
for i in range(2, n + 1): # 2번 노드부터 부모 노드 출력
    print(parent[i])

My Code 2 - BFS 

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

def bfs(now):
    q = deque() 
    q.append(now) # 큐에 노드 삽입
    while q:
        now = q.popleft() # 큐에서 현재 노드 꺼냄
        for i in graph[now]: # 현재 노드와 연결된 노드들 확인
            if parent[i] == 0: # 만약 아직 부모 노드가 없으면
                parent[i] = now # 현재 노드를 부모로 설정
                q.append(i)     # 큐에 연결된 노드를 넣어줌

n = int(input()) # 노드의 개수

graph = [[] for _ in range(n + 1)] # 그래프
for _ in range(n - 1):
    a, b = map(int,input().split()) # 연결된 두 노드의 번호
    # 양방향으로 노드 연결
    graph[a].append(b)
    graph[b].append(a)

parent = [0] * (n + 1) # 부모 노드를 저장할 list

bfs(1) # 1부터 탐색
for i in range(2, n + 1): # 2번 노드부터 부모 노드 출력
    print(parent[i])