[백준] 11725번: 트리의 부모 찾기 (python)

11725번: 트리의 부모 찾기

---

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

 

 

입력 :

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

 

 

출력 :

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

 

 

 

 

 

 

풀이)

간단하게 생각하면 쉬운 문제였는데 너무 어렵게 생각한게 

시간을 너무 많이 잡아 먹은 것 같다.

어떻게 해야 간단히 생각한 걸까?

DFS의 경우에는 깊이 우선 탐색이므로 부모 노드에서부터 자식노드로 점점 내려가는 형식을 취하고 있다.

따라서 문제에서 트리의 루트를 1이라 가정했으므로, 1번 노드에서부터 시작하여 각 노드 도착했을때,

출발한 노드가 부모노드가 되므로, 도착유무를 저장하는 visited 변수에 도착 유무가 아닌

출발 노드를 저장하면, 보다 단순하게 부모노드를 찾아낼 수 있다.

 

from collections import deque
import sys
 
def DFS(i):
    global visited
    stack.append(i)
    while stack:
        a = stack.pop()
        for i in graph[a]:
            if not visited[i]:
                # 부모 노드를 거쳐서 자식 노드로 가므로,
                # a가 i 노드의 부모가 된다.
                visited[i] = a
                stack.append(i)
 
n = int(sys.stdin.readline().strip())
graph = [[] for i in range(n + 1)]
 
# 트리를 양 방향으로 입력 받기
for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().strip().split())
    graph[a].append(b)
    graph[b].append(a)
 
# DFS 사용
stack = deque()
visited = [False] * (n + 1)
DFS(1) # 시작 노드 "1"
for i in range(2, n + 1):
    print(visited[i])

---

출처 : https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기