[DFS] 백준 11725번 “트리의 부모 찾기” Python 풀이

문제 링크

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

풀이

• 2차원 연결 리스트를 사용해, 각 노드간 연결 정보를 양방향으로 모두 저장합니다.
• 루트 노드(1)부터 연결된 노드들을 확인하며,
• 연결된 노드의 부모 노드가 없을 경우, 현재 노드를 연결된 노드의 부모 노드로 저장합니다.
• 이후, 연결된 노드들을 기반으로 다시 DFS를 진행합니다.
• 추가 사항
  • BOJ의 채점 서버에서, Python의 최대 재귀 깊이는 1,000으로 설정되어있습니다.
  • 재귀 호출 횟수가 해당 값을 넘어가게되면 RecursionError가 발생하게 됩니다.
  • 따라서, sys.setrecursionlimit()을 사용해 최대 재귀 깊이를 변경해야합니다.

코드

import sys
sys.setrecursionlimit(10**6)

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

# 부모 저장 배열
parent = [0] * (n+1)

# 양방향 연결 정보 저장
graph = [[] for _ in range(n+1)]

for _ in range(n-1):

    # 양방향 연결 정보 입력 및 저장
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)
    graph[end].append(start)

# 부모 노드 탐색
def dfs(root):

    # 현재 노드와 연결된 노드 확인
    for neighbor in graph[root]:

        # 연결된 노드의 부모가 없다면
        if (parent[neighbor] == 0):

            # 현재 노드를 연결된 노드의 부모 노드로 설정
            parent[neighbor] = root

            # 연결된 노드들 기준으로 DFS 진행
            dfs(neighbor)

# 1번 노드부터 탐색 시작
dfs(1)

# 2번 노드부터 부모 노드 번호 출력
for i in range(2, n+1):
    print(parent[i])