[#11725] 트리의 부모 찾기

RookieAND·2022년 6월 13일

BFS 백준 코테 트리

BaekJoon

목록 보기

11/42

❓ Question

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

📖 Before Start

오늘 처음 학습한 트리 자료구조 탐색에 관한 문제를 풀어보았다.

이번 문제는 트리의 부모 노드를 BFS, DFS 탐색을 통해 알아내는 문제였다.
비교적 구현이 간단한 DFS 탐색을 먼저 시도하였으나, 메모리 초과로 실패하였다.
따라서 BFS 탐색으로 문제를 재접근한 뒤 푼 끝에 이 문제를 풀 수 있었다...

✒️ Design Algorithm

부모 노드 를 어떻게 탐색할 수 있을지가 몹시 고민이었다.

N 개의 노드를 주고, 각 노드 간 간선에 대한 정보를 N-1 개에 걸쳐 입력 받는다.
해당 정보에서는 부모 자식 관계 를 유추할 수 없으니, 각 노드 별로 연결된 노드 목록을 저장한다.
그런 뒤 DFS 탐색을 통해 루트 노드인 1 부터 순차적으로 깊이 탐색을 통해, 각 노드 간 부모 노드를 구한다.

DFS 탐색 으로 루트 노드로부터 부모 노드에 대한 정보를 인계 받아 탐색해보자.

방문 여부를 나타내는 visited List와 부모 노드의 정보를 담을 parent List를 생성한다.
먼저, 루트 노드 (1번) 와 연결된 노드들의 목록 (자식 노드) 을 이차원 배열로부터 가져온다.
부모 노드에 대한 정보를 parent list에 저장한 후, 해당 자식 노드를 방문 처리 한다.
그런 뒤 해당 자식 노드에 대한 DFS 탐색을 재귀 함수로 다시 실행시킨다.

💻 Making Own Code

❌ Wrong Code

import sys
sys.setrecursionlimit(10 ** 9)

read = sys.stdin.readline
N = int(read())
tree = [list() for _ in range(N + 1)]
parent = [-1] * (N + 1)

for i in range(N-1):
    f_node, s_node = map(int, read().split())
    tree[f_node].append(s_node)
    tree[s_node].append(f_node)


def dfs(node):
    for child_node in tree[node]:
        # 해당 노드의 부모를 아직 파악하지 못했는지 판별
        if parent[child_node] == -1:
            parent[child_node] = node
            # 부모 노드가 판별되었다면, 자식 노드에 대한 dfs 탐색 진행.
            dfs(child_node)

# 1번 루트 노드부터 dfs 탐색을 진행.
dfs(1)
for i in range(2, N+1):
    print(parent[i])

하지만 DFS 탐색 의 고질적인 문제인 메모리 초과 문제에 직면하고 말았다.

결국 DFS 탐색으로는 안된다는 이야기니, 방향을 바꿔서 BFS 탐색으로 코드를 재작성하였다.
BFS 탐색으로는 부모 노드의 정보를 어떻게 인계시킬까를 많이 고민하고 또 고민했다.
결국 다른 분들이 풀이한 코드를 보고 나서야, 내가 너무 먼 길을 돌아왔다는 걸 깨달았다.

✅ Correct Code

import sys
from collections import deque

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

visited = [False] * (N + 1)
parent = [-1] * (N + 1)

tree = [list() for _ in range(N + 1)]
for i in range(N-1):
    f_node, s_node = map(int, read().split())
    tree[f_node].append(s_node)
    tree[s_node].append(f_node)


def bfs(node):
    queue = deque([node])
    while queue:
        # 해당 노드의 자식 노드 목록을 먼저 불러온다.
        child_node = queue.popleft()
        # 자식 노드들을 하나씩 순회하면서, 방문 여부를 판별한다.
        for cd_node in tree[child_node]:
            if not visited[cd_node]:
                # 방문을 하지 않았다면, 부모 노드 정보를 추가하고 방문 처리한다.
                visited[child_node] = True
                parent[cd_node] = child_node
                queue.append(cd_node)

bfs(1)
print(*parent[2:], sep='\n')

결국 자식 노드를 하나씩 순회하면서 부모 노드에 대한 정보를 담고, 방문 처리하는 방식은 같다.
지금까지 제법 여러 형식의 그래프 탐색 문제를 풀었는데, 아직 DFS 탐색을 쓴 적은 없는 것 같다.
다른 블로그를 탐색하다가 DFS를 스택 자료구조로 구현한 분이 있어, 이를 한번 더 참고하였다.

✅ Correct Code (with DFS + Stack)

import sys
from collections import deque

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

visited = [False] * (N + 1)
parent = [-1] * (N + 1)

tree = [list() for _ in range(N + 1)]
for i in range(N-1):
    f_node, s_node = map(int, read().split())
    tree[f_node].append(s_node)
    tree[s_node].append(f_node)


def dfs(node):
    stack = deque([node])
    while stack:
        # 해당 노드의 자식 노드 목록을 먼저 불러온다.
        child_node = stack.pop()
        # 자식 노드들을 하나씩 순회하면서, 방문 여부를 판별한다.
        for cd_node in tree[child_node]:
            if not visited[cd_node]:
                # 방문을 하지 않았다면, 부모 노드 정보를 추가하고 방문 처리한다.
                visited[child_node] = True
                parent[cd_node] = child_node
                stack.append(cd_node)

dfs(1)
print(*parent[2:], sep='\n')