[python] 11725, 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

코드 확인 )  https://github.com/nyunu/BaekJoon/blob/main/11724.ipynb

 

[문제]

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

 

[입력]

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

 

[출력]

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

 

[예제]

 

[풀이]

 트리에서 부모노드를 구한다 = 모든 노드를 탐색해봐야 한다 = DFS or BFS로 풀이할 수 있다 !

=> 기본적인 그래프 탐색 문제 : BFS, DFS 함수 구현이 주가 된다 !

 

💡 DFS (깊이 우선 탐색)

 

1. 재귀함수 사용 : 65708 KB / 312 ms

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000) # 해주지 않으면 recursionerror 발생

n = int(input())
graph = [[] for i in range(n + 1)]

# 그래프 입력
for _ in range(n - 1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

# 방문 노드 입력할 리스트
visit = [False] * (n + 1)
# 부모 노드를 입력해줄 리스트 (최종 결과값)
parent = [0 for _ in range(n + 1)]

# dfs 함수
def dfs(node):
  visit[node] = True # 현재 노드를 방문했다고 리스트에 표시
  for i in graph[node]: # 현재 노드의 모든 자식 노드에 대해
    if not visit[i]: # 만약 자식노드를 방문하지 않았다면
      parent[i] = node # 현재 노드가 자식노드의 부모 노드가 되고
      dfs(i) # 자식노드를 대상으로 dfs를 실행하여 자식노드를 부모노드로 갖는 노드들을 탐색

dfs(1) # 문제에서 주어진 루트노드가 1이므로 1에서 시작하여 모든 노드를 탐색

print(*parent[2:], sep = '\n') # 출력값인 부모 노드를 '\n'을 구분자로 하여 하나씩 출력

 

 가장 기본이 되는 재귀함수를 통한 dfs의 구현인데, 함수의 재귀호출 횟수가 많아지면 기본으로 설정된 재귀호출 한계에 부딪혀 실행이 되지 않는 경우가 있는 것 같다. 따라서 sys.setcursionlimit(1000000)와 같이 재귀호출의 한계를 높여주어야 런타임 에러가 나지 않고 정답처리가 가능하다. recursionerror에 부딪힌다는건 별로 좋지 않은 방식이라는건지 ... 정확히 몇으로 limit을 확장시켜야 하는건지는 모르겠다.

 

2. 스택(stack) 사용 : 52196 KB / 284 ms

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

n = int(input())
graph = [[] for i in range(n + 1)]

# 그래프 입력
for _ in range(n - 1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visit = [False] * (n + 1) # 방문 노드 표시 리스트
parent = [0 for _ in range(n + 1)] # 부모 노드 표시 리스트

# dfs 함수
def dfs(node):
  visit[node] = True
  stack = deque([node])
  while stack: # stack이 빌 때까지 반복
    v = stack.pop() # 가장 마지막에 입력된 노드를 꺼내옴 (stack의 성질 : FILO)
    for i in graph[v]: # v노드의 자식노드들에 대해
      if not visit[i]: # 만약 아직 방문하지 않은 노드가 있다면
        stack.append(i) # 방문하지 않은 노드를 stack에 추가
        visit[i] = True # 방문했다고 표시
        parent[i] = v # 부모 노드는 v 

dfs(1) # 루트노드가 1이므로 1부터 시작하여 모든 노드 탐색

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

 

 collections의 deque 함수를 사용해 스택을 구현했다. 아무래도 재귀적으로 함수가 호출되는 것이 아니라 함수를 한번 호출하여 그 안에서 while문으로 처리하기 때문에 시간이나 메모리 측면에서 더 앞선 재귀함수보다 나은 결과가 나온 것이 아닐까 추측된다 !

 

💡 BFS (너비 우선 탐색) : 52480 KB / 292 ms

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

n = int(input())
graph = [[] for i in range(n + 1)]

# 그래프 입력
for _ in range(n - 1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

visit = [False] * (n + 1) # 방문 노드 표시
parent = [0 for _ in range(n + 1)] # 부모 노드 표시

# bfs 함수
def bfs(node):
  visit[node] = True # node의 방문 표시
  queue = deque([node]) # queue를 사용하여 bfs 구현
  while queue: # queue에 원소가 들어있는 동안
    v = queue.popleft() # queue에서 가장 처음 입력된 값 (가장 왼쪽에 있는 값)을 v로
    for i in graph[v]: # v의 모든 자식노드에 대해
      if not visit[i]: # 만약 방문하지 않은 노드가 있다면
        queue.append(i) # queue에 포함시키고
        parent[i] = v # 부모 노드는 v
        visit[i] = True # 방문 표시

bfs(1) # 루트 노드인 1부터 시작해 모든 노드 탐색

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

 

 collections의 deque 함수를 사용해 큐를 구현했다. 앞선 stack과 다른 점은 stack은 가장 오른쪽의 값을 빼왔다면, queue는 가장 왼쪽의 값(가장 처음에 입력된 값)을 빼오며 while문이 반복된다는 점이다. 그외의 방식은 앞선 stack과 동일하다.