백준 11725 트리의 부모 찾기 실버2

 

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

 

예제 입력1

7
1 6
6 3
3 5
4 1
2 4
4 7

 

 

예제 입력2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

 

 

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

예제 출력1

4
6
1
3
1
4

 

예제 출력2

1
1
2
3
3
4
4
5
5
6
6

 

 

코드

풀이1 DFS

import sys
sys.setrecursionlimit(10**6)

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


v = [0] * (N+1)						# 방문 배열
tree = [[] for _ in range(N+1)]		# 간선 정보 저장할 공간
p = [0] * (N+1)						# 부모 노드 저장

# 간선 정보 저장
for _ in range(N-1): 
    n1, n2 = map(int, sys.stdin.readline().split())
    tree[n1].append(n2)
    tree[n2].append(n1)

def dfs(num):
    v[num] = 1
    for i in tree[num]:
        if v[i] == 0:
            p[i] = num
            dfs(i)

dfs(1)

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

 

 

코드 설명

import sys
sys.setrecursionlimit(10**6)

- 파이썬 인터프리터가 허용하는 재귀 호출의 최대 깊이를 설정

- 일반적으로 설정되어있는 재귀의 깊이 제한 때문에 RecursionError 가 발생할 수 있어서 사용

 

특이한 점

- PyPy3로 하면 메모리 초과가 발생함 : 재귀 호출 스택의 메모리 사용량이 Python보다 훨씬 크기 때문

 

 

풀이2 DFS

 

이전과 메모리 사용량은 같은데,

`N = int(sys.stdin.readline())`이 빠졌더니 시간이 엄청 늘었다

import sys
sys.setrecursionlimit(10**6)

N = int(input())

v = [0] * (N+1)
tree = [[] for _ in range(N+1)]
p = [0] * (N+1)


# 인접 노드 저장
for _ in range(1,N) :
    n1,n2 = map(int,input().split())
    tree[n1].append(n2)
    tree[n2].append(n1)


# 트리 순회
def dfs(num) :
    v[num] = 1
    for i in tree[num] :
        if v[i] == 0 :      # 방문 안했다면
            p[i] = num      # 직전 노드를 부모 노드에 저장
            dfs(i)          # 새로운 노드 탐색
    
# 트리 호출
dfs(1)

# 정답 출력
for i in range(2,N+1) :
    print(p[i])

 

 

풀이3 BFS

 

-` N = int(sys.stdin.readline())`를 안썼더니 시간은 여전히 느리지만, Q를 사용함으로써 메모리는 줄였다

from collections import deque

N = int(input())


tree = [[] for _ in range(N+1)]
p = [0] * (N+1)


# 인접 노드 저장
for _ in range(N-1) :
    n1,n2 = map(int,input().split())
    tree[n1].append(n2)
    tree[n2].append(n1)


# 트리 순회
def bfs(start) :
    q = deque([start])
    while q :
        current = q.popleft()
        for next in tree[current] :
            if p[next] == 0 :
                p[next] = current
                q.append(next)

bfs(1)

# 정답 출력
for i in range(2,N+1) :
    print(p[i])

 

이 문제의 포인트

이 문제의 포인트는 이전 노드가 부모 노드인 것을 알아채는 것!