[파이썬/Python] 백준 11725번: 트리의 부모 찾기

📌 문제 : 백준 11725번

---

📌 문제 탐색하기

N : 노드의 개수 $(2 ≤ N ≤ 100,000)$

N개의 노드 중 두번째 노드부터 부모 노드를 찾아 출력하는 문제이다.

문제 풀이

먼저 각 노드의 부모 노드 정보를 저장할 리스트를 정의한다.

각 노드간 연결 정보를 입력받고 DFS/BFS로 연결 정보를 탐색한다.

연결 정보를 입력받을 때 그래프 간 방향성은 가지고 있지 않기 때문에 양쪽 노드 모두에 연결 정보를 입력해준다.

노드 1부터 BFS를 수행하면서 부모 노드가 무엇인지 정해지지 않았을 때 해당 노드를 부모 노드로 지정해준다.

가능한 시간복잡도

그래프 입력 → $O(N-1) = O(N)$
BFS 수행 → $O(N + (N-1)) = O(N)$

최종 시간복잡도
$O(N)$로 최악의 경우 $O(100,000)$이 되어 1초 내 연산 가능하다.

알고리즘 선택

노드 1부터 BFS 탐색하여 부모 노드 찾기

---

📌 코드 설계하기

1. BFS 구현
2. N 입력
3. 부모 노드 저장 리스트 정의
4. 연결 정보 인력
5. BFS 수행
6. 결과 출력

---

📌 시도 회차 수정 사항

1회차

---

📌 정답 코드

### BFS 이용
import sys
from collections import deque

input = sys.stdin.readline

def bfs(v):
    # 큐 정의
    queue = deque([v])
    # 큐 빌 때까지 반복
    while queue:
        v = queue.popleft()
        # 연결 정보 확인하면서 부모 노드 채우기
        for i in graph[v]:
            if parents[i] == 0:
                parents[i] = v
                queue.append(i)


# N 입력
N = int(input())

# 부모 노드 저장할 리스트 정의
parents = [0] * (N+1)

# 그래프 정의
graph = [[] for _ in range(N+1)]

# 연결 정보 저장
for _ in range(N-1):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

# bfs 수행
bfs(1)

# 2번째 노드부터 부모 노드 출력
for i in range(2, N+1):
    print(parents[i])

### DFS 이용
import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

# N 입력
N = int(input())

# 그래프 정보 입력
graph = []

parents = [0] * (N+1)

for _ in range(N+1):
    graph.append([])

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

def DFS(v):
    for i in graph[v]:
        if not parents[i]:
            parents[i] = v
            DFS(i)

DFS(1)

for i in range(2, N+1):
    print(parents[i])

• 결과