[백준] 🌳 11725: 트리의 부모 찾기 - BFS로 뿌리부터 차근차근!

“실패는 성공의 어머니, 디버깅은 개발의 아버지!”

💻 백준 11725: 트리의 부모 찾기

• 문제 링크: https://www.acmicpc.net/problem/11725
• 알고리즘 분류: 트리, 너비 우선 탐색, 그래프 탐색

---

🤔 이 문제, 어떻게 풀까? (요약)

1. 첫인상: “트리? 클래스 만들어서 풀면 되겠네!” 👉 이진 트리로 착각해서 런타임 에러! 😭
2. 깨달음: “아, 트리는 그냥 그래프였지!” 👉 BFS로 방향 전환!
3. 해결: 루트(1)부터 BFS를 돌면서, 방문하지 않은 노드를 만날 때마다 현재 노드를 부모로 기록해주니 간단하게 해결됐다. 성공! 🎉

---

문제 소개 🧐

루트가 없는 트리가 주어지는데, 1번 노드를 루트라고 딱 정해줬다. 이때 각 노드의 부모가 누군지 찾아 출력하면 되는 문제다.

입력 📝

• 첫 줄에는 노드 개수 N이 주어진다.
• 다음부턴 그냥 연결된 노드 두 개씩 N-1 줄에 걸쳐서 나온다.

출력 📤

• 2번 노드부터 순서대로, 각자의 부모 노드 번호를 출력하면 된다.

제한 ❌

• 시간: 1초
• 메모리: 256MB

---

첫 번째 시도: “내가 직접 트리를 만들어볼까?” 👊

Idea

처음엔 의욕이 넘쳤다. Tree 클래스를 만들어서 parent, left, right 속성을 주고, 1번 노드부터 차곡차곡 자식들을 연결해주면 되겠다고 생각했다. 이땐 몰랐다. 이 트리가 내 생각보다 훨씬 자유로운 영혼이었다는 것을…

Code

import sys
from collections import deque

n =  int(sys.stdin.readline().rstrip())
dic = {}
q = deque()

class Tree:
    parent:"Tree"
    own_num:int
    left:"Tree"
    right:"Tree"

    def __init__(self,  own_num:int, parent:"Tree" = None):
        self.own_num = own_num
        self.parent = parent
        self.left = None
        self.right = None
    
    def set_child(self, child:"Tree"):
        if self.left is None:
            self.left = child
        elif self.right is None:
            self.right = child
        else:
            return False
        return True
    
    def get_right(self):
        return self.right.own_num if self.right is not None else 0
    def get_left(self):
        return self.left.own_num if self.left is not None else 0
    def get_parent(self):
        return self.parent.own_num if self.parent is not None else 0

tree_list = [None] * (n + 1)
tree_list[1] = Tree(1)

for i in range(1, n):
    a, b = map(int, sys.stdin.readline().split())
    if dic.get(a) is None:
        dic[a] = [b]
    else:
        dic[a].append(b)
    if dic.get(b) is None:
        dic[b] = [a]
    else:
        dic[b].append(a)

root = tree_list[1]
q.append(root)
val_q= deque()
while q:
    node = q.popleft()
    values = dic.get(node.own_num)
    for val in values:
        val_q.append(val)

    while node.right is None and val_q:
        val = val_q.pop()
        if val == node.get_left() or val == node.get_right() or val == node.get_parent():
            break
        n_node = Tree(val, node)
        node.set_child(n_node)
        tree_list[val] = n_node
        q.append(n_node)

for i in range(2, n + 1):
    print(tree_list[i].get_parent())

Result

• 런타임 에러! ⏰
• 예제는 잘 돌아갔는데, 제출하니 바로 런타임 에러가 떴다. 왜 틀렸는지 생각해보니, 예제엔 자식이 셋 이상인 노드가 없어서 내가 이진 트리라고 착각했던 거다. 실제로는 한 부모 아래 자식이 여럿일 수 있었다. 내 코드는 left, right 밖에 없으니 당연히 에러가 날 수밖에.

---

두 번째 시도: “정신 차리고, BFS” ✨

Idea

첫 시도의 실패로 깨달음을 얻었다. “트리는 사이클 없는 그래프다!” 이 명제를 떠올리고 나니 길이 보였다. 루트 노드인 1번부터 BFS를 돌면서 탐색하는 노드들의 부모를 기록해주면 되는 거였다.

1. 인접 리스트로 그래프를 만든다.
2. parent 배열을 만들어 각 노드의 부모를 저장한다. (방문 체크용으로도 사용!)
3. 큐에 1번 노드를 넣고 BFS 시작!
4. 큐에서 꺼낸 노드와 연결된 녀석들 중, 아직 부모가 없는(방문 안 한) 노드를 발견하면, 현재 노드를 부모로 기록하고 큐에 쏙 넣어준다.

Code

import sys
from collections import deque

def bfs(graph, start_node, parent):
    queue = deque([start_node])
    parent[start_node] = start_node  # 루트는 자기자신을 부모로... (방문표시)
    
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if parent[v] == 0:  # 아직 부모가 없니?
                parent[v] = u   # 내가 너의 부모다!
                queue.append(v)

# (입력 처리 및 함수 호출 부분은 동일)

Result

• 성공! ✅
• BFS로 접근하니 모든 노드를 딱 한 번씩만 방문해서 아주 효율적으로 부모를 찾을 수 있었다. 역시 기본기가 중요하다!

---

오늘의 교훈 🤔

• 섣부른 일반화는 금물: “트리? 아~ 이진 트리!” 하고 넘겨짚었던 게 패인이었다. 문제에 명시되지 않은 조건은 스스로 만들지 말자.
• 예제는 거들 뿐: 예제는 그냥 참고 자료일 뿐, 모든 경우를 대변해주지 않는다. 항상 더 일반적이고 짓궂은 케이스가 숨어있을 거라고 생각하며 코드를 짜야겠다.