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

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

 

 

 

📌  문제 접근

처음에 트리를 그린 후 부모를 찾으려고 하니, 기준이 없어서 도대체 부모를 어떻게 찾아야하나 한참 헤멨다.

그러나 문제를 다시 읽어보니

"루트는 1이다."

라는 조건이 있었다. (문제를 잘 읽자 .. )

이걸 기반으로 1번 노드부터 탐색했다.

 

---

🔍 문제 풀이

1. DFS 

처음에는 DFS로 풀었다. 현재 노드에서 연결된 노드로 이동하면서,
아직 방문하지 않은 노드에 대해 방문처리 + 부모 저장을 동시에 진행한다.

하지만  RecursionError (런타임 에러) 가 발생해서 재귀제한을 늘려줘야했다.

 

import sys
sys.setrecursionlimit(10**6)

def dfs(n):
    if n > N+1:
        return

    for i in graph[n]:
        if visited[i] == 0:
            visited[i] = n
            dfs(i)


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

# print(graph)
visited = [0,1]+[0]*(N-1)
dfs(1)

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

 

 

2. BFS

DFS코드로 채점을 하니 꽤 오래걸려서 BFS로도 다시 풀어보았다.
근데 BFS가 더 오래걸렸다 .. 

from collections import deque

def bfs(n):
    q = deque([n])
    visited[n] = 1

    while q:
        cn = q.popleft()

        for node in graph[cn]:
            if visited[node] == 0:
                q.append(node)
                visited[node] = cn


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

# print(graph)
visited = [0]*(N+1)
bfs(1)

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