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

문제

11725번: 트리의 부모 찾기

 

---

풀이

예제 입력 1에 대한 트리

      1
     / \
    6   4
   /   / \
  3   7   2
 /
5

 

BFS

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

# 노드의 개수 N (2 ≤ N ≤ 100,000)
N = int(input().rstrip())

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

for i in range(1, N):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

parents = [0] * (N+1) # 각 노드의 부모 노드를 저장할 리스트
visited = [False] * (N+1) # 방문 여부를 저장하는 리스트

def bfs():
    queue = deque()
    queue.append(1)
    visited[1] = True

    while queue:
        node = queue.popleft()
        for child in tree[node]:
            if not visited[child]:
                parents[child] = node
                visited[child] = True
                queue.append(child)

bfs()

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

아이디어

• 입력되는 정보를 바탕으로 인접 리스트 형태의 트리를 만든다.
• 루트 노드 = 부모가 없는 노드를 말한다. 문제에서 트리의 루트는 1이다. 루트 노드의 부모는 0이다.-> visited 방문 체크를 해주지 않으면 루트 노드의 부모가 잘못 표시된다. 문제는 2번 노드부터 출력하니 정답 여부에 상관은 없다.
• 부모 노드를 표시할 리스트를 선언하고 루트 노드인 1부터 bfs 탐색을 시작한다.
• 해당 노드와 연결된 자식 노드들에 대해 반복하면서, 방문하지 않은 자식 노드에 대해 부모를 설정하고 방문 처리, 큐에 추가한다.
• 2번 노드부터 부모를 한 줄씩 출력한다.

 

DFS

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

N = int(input().rstrip())

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

for i in range(1, N):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

parents = [0] * (N+1)

visited = [False] * (N+1)
visited[1] = True

def dfs(node, parent):
    parents[node] = parent
    for child in tree[node]:
        if not visited[child]:
            visited[child] = True
            dfs(child, node)

dfs(1, 0)

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

 

DFS는 항상 재귀로.

RecursionError가 발생하므로 recursionlimit을 늘려주고 PyPy3로 제출해야 한다.

노드의 개수 N이 100,000까지 갈 수 있는 점을 고려해 파이썬 재귀 제한을 늘려줘야 한다. 기본 1000

 

시간 복잡도

BFS, DFS 모두 각 노드에 한 번씩 방문하여 부모를 설정하므로 O(N_노드의 개수 + N-1_간선의 개수) => O(N)

 

공간 복잡도

O(N)

 

 

 

너무 어렵다.. 나만 어렵나?.. 반복을 더 해야겠다!