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

난이도 : Silver2
Link : https://www.acmicpc.net/problem/11725
Tag : 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
풀이일자 : 2024년 8월 29일

📌 문제 탐색하기

N : 노드의 갯수
첫째 줄 부터 입력 설명
1 6 : 1번 노드와 6번 노드가 이어져 있다.
라는 뜻이다.

이 문제에서는 이어져 있는 노드들을 알려주고 각 노드의 부모 노드를 출력하는 것이 목적이다.
해당 노드에서는 루트가 없는 트리 이고 이때 트리의 루트를 1이라고 정했기 때문에 1의 부모 노드는 존재하지 않는다. 따라서 문제에서도 2번 노드부터 순서대로 부모 노드를 출력하는 것이다.

가능한 시간복잡도

노드의 갯수는 2 <= N <= 100,000 이기 때문에 간선 수를 E라고 가정할때 시간복잡도는 O(N+E) 로 DFS와 BFS를 통해 문제를 탐색할 수 있을것이다.

📌 문제 접근 방법

먼저 각 리스트의 인덱스로 1번 인덱스에 1번 노드의 연결된 노드를, 2번 인덱스에 2번 노드의 연결된 노드를 저장하고자 한다.
이렇게 2차원 배열을 통해 인덱스 별로 연결된 노드들을 저장해 놓는다면 DFS를 통해 재귀함수로 모든 노드들을 탐색할 수 있다.

입력받은 두 수 a,b 에 대해서 인덱스 별로 연결된 노드들을 저장하려고 했기 때문에 다음과 같이 저장할 수 있다.

tree[a].append(b)
tree[b].append(a)

DFS의 함수 구현은 재귀 함수로 구현을 한다.
입력받은 노드 부터 탐색을 시작하고, 입력 받은 노드에서 인접한 노드에 대한 방문을 체크한다.
만일 방문 하지 않은 노드라면 부모 노드임을 알 수 있다.
따라서 방문하지 않았다면 visited[] 배열에 해당 노드를 저장하고, 함수를 재귀 호출한다.

📌 코드 설계하기

1. N을 입력받는다.
2. tree배열을 n+1개 만큼 생성한다 (인덱스 별로 노드를 저장할 것이기 때문)
3. n-1만큼 반복하여 tree 인덱스에 이웃한 노드들을 저장한다.
4. visited[] 배열을 n+1개 생성한다.
5. DFS 함수를 구현한다
   • 해당 노드를 탐색한 적이 없다면 visited[]배열에 해당 노드를 저장한다.
   • DFS 함수를 해당 노드로 재귀 호출한다.
6. DFS 함수를 1부터 호출한다. (첫번째 노드부터 DFS 탐색)
7. 두번째 노드부터 출력하기 위해 2부터 n+1까지 반복해 visited 배열을 출력한다.

📌 시도 회차 수정 사항

Recursion Error

sys.setrecursionlimit(1000000) 재귀 리미트 제한을 제대로 하지 않아 오류가 발생하였다.

📌 정답 코드

import sys
sys.setrecursionlimit(1000000)

n = int(sys.stdin.readline())
tree = [[] for i in range(0,n+1)]

for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b) #a번 노드와 인접한 노드
    tree[b].append(a) #b번 노드와 인접한 노드

visited = [0] * (n+1) #방문 노드 즉 부모노드

def dfs(node):
    for i in tree[node]:
        if visited[i] == 0:
            visited[i] = node
            dfs(i)

dfs(1) #첫번째 노드부터 dfs

for a in range(2,n+1): # 두번째 노드 부터 출력
    print(visited[a])