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

문제

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

입력

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

출력

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

 

출처

• 문제를 만든 사람: baekjoon
• 잘못된 조건을 찾은 사람: jh05013

! 문제 생각&풀이 !

각 노드의 부모 노드 번호를 찾아가야하므로 깊이가 어느정도인지 찾아야한다고 생각했기에 DFS를 활용한 탐색으로 문제를 풀어보면 어떨까부터 생각을 했다.

 

우선은 간선 정보 입력을 양방향 연결로 받아서 arr에 각 정점의 연결된 정점들을 담아서 시작했다.

루트 노드부터 시작하여 깊이 우선 탐색 실행하는 함수를 만들었고,

현재 방문 중인 노드를 타나내는 v를 표시했다. 현재 노드 v에서 연결된 모든 노드에 대해 반복을 하여 만약 현재 노드 i가 방문하지 않았다면 그 노드 i의 부모 노드를 v로 설정해서 부모 노드를 찾아갔다. 마지막에는 재귀로 깊이우선탐색을 계속 수행하게하였다.

 

처음 제출했던 코드에서 런타임에러 중 리커전 에러가 발생했다. 리커전에러는 최대 재귀한도 깊이 에러라고 하여 구글에서 조금 찾아보니 import sys를 가져와 입력 부분을 조금 수정해주고 리커전에러 방지를 위한 sys.setrecursionlimit(10**7)이라는 것을 넣어 재귀의 한도를 설정해주면 문제가 해결된다고하여 똑같이 따라해보았다. 결론적으로 잘 수행되었다.

! 첫 Code ! (런타임에러: 리커전에러)

# 트리의 부모찾기 S2
def solve(v, arr, visited):
    for i in arr[v]:
        if not visited[i]:
            visited[i] = v
            # print(f'visited :', visited)
            solve(i, arr, visited)

# N
N = int(input())
arr = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
# print(arr)
visited = [0] * (N+1)
parent = [0 for _ in range(N+1)]

solve(1, arr, parent)
# print(parent)
for i in range(2, N+1):
    print(parent[i])

 

! 추가 수정 Code ! (통과)

# 트리의 부모찾기 S2
import sys
sys.setrecursionlimit(10**7) # 런타임에러: 리커전에러 방지
def solve(v, arr, visited):
    for i in arr[v]:
        if not visited[i]:
            visited[i] = v
            # print(f'visited :', visited)
            solve(i, arr, visited)

# N
N = int(input())
arr = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)
# print(arr)
visited = [0] * (N+1)
parent = [0 for _ in range(N+1)]

solve(1, arr, parent)
# print(parent)
for i in range(2, N+1):
    print(parent[i])