[백준 11725] 트리의 부모 찾기

문제
루트 없는 트리가 주어진다.
이때 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드를 구하라

입력
첫째 줄에 노드의 개수가 주어진다.
둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 입력된다.

출력
2번 노드부터 부모 노드 번호를 출력한다.

---

접근

트리를 이해하고자 문제를 풀었다.

기본적으로 트리는 데이터를 삽입, 삭제하는 기능보다 계층적 관계를 표현하기 위한 자료구조이다. 

이러한 계층적 관계를 파이썬으로 어떻게 구현해야 할지 익혔다.

이 문제에서는 2차원 리스트를 활용하였다. 바깥의 큰 리스트에 포함되어있는 1차원 리스트는 자신의 자식노드 번호를 담고있다. 

문제에서 1번이 루트노드라고 정했기 때문에 1번에 들어있는 자식노드부터 탐색을 진행하여 각각의 부모노드를 구하도록 하였다. 탐색은 스택을 활용한 DFS로 하였다.

 

구현

노드의 개수를 입력받고 tree라는 2차원 리스트를 생성한다. 이곳에 각각의 노드들의 자식노드들을 담을 것이다.

N = int(input())
tree = [[] for _ in range(N+1)]

 

노드들의 관계를 입력받고 무방향 그래프처럼 서로를 가리키도록 표현을 하였다. 

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

 

스택을 활용하여 탐색이 진행되며 처음에 1번을 담아 1번부터 자식노드들을 탐색한다.

그리고 방문한 노드는 리스트 visited의 각 노드의 자리에 True로 표시한다.

리스트 answer의 경우 각 노드들의 부모 노드 번호를 담을 것이다.

stack = []
stack.append(1)
answer = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]

visited[1] = True

 

스택이 빈 리스트가 될 때까지 반복을 하며 DFS 탐색을 한다.

스택에서 노드를 꺼내어 부모 노드로 설정한다. 이후 해당 부모 노드의 자식노드들을 탐색하여 방문하지않은 노드를 찾고 해당 노드의 부모노드를 추가한다. 

그리고 찾은 자식 노드는 스택에 넣고 다시 반복을 진행한다.

while stack:
    parent = stack.pop()
    for child in tree[parent]:
        if not visited[child]:
            visited[child] = True
            answer[child] = parent
            stack.append(child)

---

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
tree = [[] for _ in range(N+1)]

# 루트가 1인 트리 생성
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

stack = []
stack.append(1)
answer = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]

visited[1] = True


while stack:
    parent = stack.pop()
    for child in tree[parent]:
        if not visited[child]:
            visited[child] = True
            answer[child] = parent
            stack.append(child)

for idx in range(2, N+1):
    print(answer[idx])