TIL) 11725 트리의 부모 찾기

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

🎄 트리의 부모 찾기

백준 11725 트리의 부모 찾기 : https://www.acmicpc.net/problem/11725

💡 아이디어

• 루트 노드부터 리프 노드까지 내려가면서 차례대로 stack에 담는다.
• 끝까지 간 후에 거꾸로 올라오면서 stack[-1]의 부모가 stack[-2]라는 것을 parents 리스트에 저장한다.
• 위 과정을 dfs() 함수를 이용해서 구현한다.

🧐 디버깅용 코드

N = int(input())

graph = { i : [] for i in range(1, N+1)}


for _ in range(N-1):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)
print(graph)
parent = [0]*(N+1)
stack = []


def dfs(i):
    global parent, stack
    stack.append(i)
    for j in graph[i]:
        if j not in stack:
            print('dfs 이전:', stack)
            dfs(j)
            print('                     dfs 이후:', stack)
            parent[stack[-1]] = stack[-2]
            stack.pop()

dfs(1)

print(stack)
print(parent)

• 디버깅을 위해서 dfs() 함수 전과 후에 stack을 출력해보았다.
• dfs 이전의 스택에 노드가 차례대로 쌓였다가 리프 노드에 도달한 후, dfs 이후의 스택에서 노드가 하나씩 빠져나가는 것을 확인할 수 있다.

🎀 제출 코드

import sys

sys.setrecursionlimit(10**6)

N = int(input())

graph = {i: [] for i in range(1, N+1)}

for _ in range(N-1):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

parent = [0]*(N+1)
stack = []
visited = [False]*(N+1)
array = []

def dfs(i):
    global parent
    stack.append(i)
    visited[i] = True
    for j in graph[i]:
        if not visited[j]:
            dfs(j)
            array.append((stack.pop(), stack[-1]))
            # parent[stack[-1]] = stack[-2]
dfs(1)
array.sort()

for i in range(N-1):
    print(array[i][1])