[백준] 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

dfs를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, root가 없는 트리가 주어지는데 이때, 1번 node를 root로 가정했을 때, 각각의 노드들의 parent 노드가 무엇이 되는지를 return 해야 합니다. (트리의 연결 상태는 단순히 연결이 되어있다 라는 정보로만 주어집니다.)

 

<Solution>

우선 이 문제는 node나 tree class를 만들 필요가 없습니다. 마치 트리를 구현해야 하는 문제 같지만 dfs를 통해 충분히 해결 할 수 있습니다. 

• 트리의 정보를 인접 리스트 형태로 구성합니다.
• 1번 노드로 부터 dfs를 하며 parent를 갱신합니다.

이 과정을 통해 해결 할 수 있습니다. 

 

간단한 예시를 통해 살펴봅시다. 

위와 같은 노드의 상태에서는 

inital state
stack : [1]
parent : [0, 0, 0, 0, 0, 0, 0, 0]
visited : [False, False, False, False, False, False, False, False]    
----------------------------------------
stack : [4, 6]
parent : [0, 0, 0, 0, 1, 0, 1, 0]
visited : [False, True, False, False, False, False, False, False]     
----------------------------------------
stack : [4, 3]
parent : [0, 0, 0, 6, 1, 0, 1, 0]
visited : [False, True, False, False, False, False, True, False]      
----------------------------------------
stack : [4, 5]
parent : [0, 0, 0, 6, 1, 3, 1, 0]
visited : [False, True, False, True, False, False, True, False]       
----------------------------------------
stack : [4]
parent : [0, 0, 0, 6, 1, 3, 1, 0]
visited : [False, True, False, True, False, True, True, False]        
----------------------------------------
stack : [2, 7]
parent : [0, 0, 4, 6, 1, 3, 1, 4]
visited : [False, True, False, True, True, True, True, False]
----------------------------------------
stack : [2]
parent : [0, 0, 4, 6, 1, 3, 1, 4]
visited : [False, True, False, True, True, True, True, True]
----------------------------------------
stack : []
parent : [0, 0, 4, 6, 1, 3, 1, 4]
visited : [False, True, True, True, True, True, True, True]

다음과 같이 매번 pop한 element를 parent로 갱신시켜 주는 dfs를 통해 올바른 parent array를 구성할 수 있음을 알 수 있습니다. 

 

실제 구현은 아래와 같습니다.

import sys

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

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

for _ in range(N-1):
    a, b = list(map(int, sys.stdin.readline().rstrip().split()))
    connection_graph[a].append(b)
    connection_graph[b].append(a)

# remove same element
for i, e in enumerate(connection_graph[:]):
    connection_graph[i] = list(set(e))

# dfs
stack = [1]
parent = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
# print('----------------------------------------')
# print('inital state')
# print(f'stack : {stack}')
# print(f'parent : {parent}')
# print(f'visited : {visited}')


while(stack):
    node_num = stack.pop()

    if visited[node_num]:
        continue

    visited[node_num] = True

    for e in connection_graph[node_num]:
        if not visited[e]: # not visied
            parent[e] = node_num
            stack.append(e)
        else:
            continue
    # print('----------------------------------------')
    # print(f'stack : {stack}')
    # print(f'parent : {parent}')
    # print(f'visited : {visited}')
for parent_ in parent[2:]:
    print(parent_)