[Python] 백준 11725 트리의 부모 찾기

 

문제 분석

• 루트 없는 트리가 주어지고, 이때 트리의 루트를 1이라고 했을 때
• 각 노드의 부모를 구하는 프로그램
• 트리상으로 연결된 두 정점이 제공될 때
• 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

풀이

1. 트리에서 각 노드의 부모를 찾는 법
루트 노드가 주어졌을 때 각 노드들의 부모는 어떻게 찾을 수 있을까?
→ 루트 노드부터 시작해서 각 노드와 연결된 간선들을 차례로 탐색
루트 노트부터 내려오면서 탐색하면 각 노드와 연결된 반대푠 노드가 부모-자식 관계임을 알 수 있다.

연결된 노드를 순차적으로 탐색하는데는 bfs / dfs 두가지 방법 모두 가능 → bfs

루트 1에 연결된 간선은 1,6 / 4,1 두가지 이다.
따라서 1번과 연결된 두 노드 4,6은 부모노드가 1로 정해짐

par[4] = 1
par[6] = 1

그 후 큐에 4, 6 노드를 넣는다.

이후에 4번 노드와 연결된 간선을 찾으면, 4,1 (1번 노드) / 2,4 (2번 노드) 두가지이다.
이때 1번 노드는 이미 부모가 정해진 상태이기 때문에 더 탐색하지 않고, 
2번 노드만 부모를 4로 표기하고 큐에 삽입

par[2] = 4

다음으로 6번 노드와 연결된 간선 탐색 : 1,6 / 6,3
이 때 6번 노드와 연결된 1번 노드는 이미 부모가 정해진 상태이니 탐색하지 않고,
3번 노드만 부모를 6으로 표기하고 큐에 삽입

이제 bfs 순회하며 각 노드의 부모 노드를 찾으면 된다.

2. 간선 정보 입력받기

그래프 문제는 두 가지 방법으로 간선의 정보를 입력 받을 수 있다.

• 인접리스트
• 인접 행렬

🍯 TIP
간선의 정보의 개수가 작을 경우 인접 리스트로 입력 받는 것이 훨씬 유리하다.
모든 행렬을 저장 받지 않아 메모리 효율도 좋고, 마찬가지로 모든 행렬을 탐색하지 않아도 되어 간선 탐색 시간도 절약된다.

이 문제에서는 인접 리스트로 입력
+) 트리이기 때문에 양방향 간선으로 입력을 받아야 한다.

3. 시간 복잡도

인접리스트에서 bfs의 시간복잡도는 O(V+E)이다.

• V : 정점의 개수
• E : 간선의 개수

이 문제에서 정점의 개수는 N, 간선은 N-1개 이므로 결과적으로 O(N)의 시간복잡도가 필요하다.
N은 최대 100,000으로 시간 안에 가능한 복잡도이다.

 

코드 설계

1. input을 받아 그래프로 저장
2. bfs 탐색을 위한 큐를 만들고, 초기 값 설정
3. bfs 탐색 진행 & 방문 여부는 부모 노드가 설정 되었는지 여부로 한 번에 체크

 

정답 코드

import sys
input = sys.stdin.readline
from collections import deque

# 1. 입력을 받아서 그래프로 저장
n = int(input())
arr = [[] for _ in range(n+1)] # 인접 리스트 : 노드 수만큼 배열 준비

for _ in range(n-1) : # 간선 정보를 읽어서 양방향 연결
    x, y = map(int, input().split())
    arr[x].append(y)
    arr[y].append(x)

# 2. bfs 탐색을 위한 큐를 만들고, 초기값 설정
now = 1 # 시작 노드
q = deque()
q.append(1) # 루트 노드를 큐에 넣음

parent = [0 for _ in range(n+1)] # 부모 노드 저장 배열
parent[1] = 1 # 루트 노드의 부모를 자기 자신으로 설정

# 3. bfs 탐색을 진행 한다. 방문 여부는 부모 노드가 설정 되었는지 여부로 한 번에 체크
while q :
    now = q.popleft() # 현재 노드
    for x in arr[now] : # 현재 노드와 연결된 노드 확인
        if parent[x] == 0 : # 아직 방문하지 않은 노드라면
            parent[x] = now # 부모 저장
            q.append(x) # 큐에 추가
for i in range(2, n+1) :
    print(parent[i])