[BOJ] 11725번 : 트리의 부모 찾기 - 파이썬(Python)

문제 해석

---

루트 노드가 없는 트리가 있는데 트리의 루트를 1이라고 가정했을때, 각 노드의 부모를 구한다는 상황이다.

BFS나 DFS를 이용해서 탐색을 했을때 해당 노드가 방문처리되기 이전의 노드가 부모노드라고 추측했다.

 

 

문제 풀이

---

import sys
from collections import deque

N = int(sys.stdin.readline().rstrip())

graph = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)


visited = [0 for _ in range(N + 1)]

deq = deque()

# 루트 노드를 1로
deq.append(1)


while deq:
    x = deq.popleft()
    for y in graph[x]:
        if visited[y] == 0:
            visited[y] = x
            deq.append(y)

for v in visited[2:]:
    print(v)

 

 

노드의 방문처리를 할 때 시작 노드 1을 포함해서 모든 노드의 부모 노드를 리스트 visited에 저장했다.

 

하지만 문제에서 원하는 것은 시작 2번 노드부터의 부모노드이기 때문에 

 

노드의 번호와 인덱스를 맞추기 위해 비워둔 0과 시작 노드의 인덱스 1을 제외한 2번 인덱스 부터의 값이 문제의 답이라고 볼 수있다.