문제

예제 입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

4
6
1
3
1
4

문제 이해

루트가 1인 트리라고 가정한다. 예제 1번을 기준으로 시각화를 한다.

대충 이런 형태가 될 것이다. 아직 다른 자료구조와 알고리즘에 대해서 많이 공부하지 않아서 잘 모르지만, 그래프탐색 문제는 시각화해서 생각해보면 충분히 도움된다. 경험상 대부분의 문제는 머리만으로 생각하기보단 노트로 끄적이면서 생각하는게 100배는 도움이 된다. 약간 수학문제와 비슷하다. 끄적이다보면 답이 보일때가 있다.

아무튼 각 노드의 부모 번호를 확인해야한다. 그러기 위해서 answer라는 1차원 리스트를 만들고 거기에 값을 넣어줄 것이다. DFS호출은 노드 1을 기준으로 메인에서 한번만 호출해서 모든 노드를 탐색하면 된다.

여기서 노드의 갯수는 최대 10만개이기 때문에 빈리스트에 append해주는 방식으로 graph를 만들어줘야 한다.

코드

# 백준 11725번 트리의 부모 찾기

def DFS(idx):
    global graph, visited, answer
    visited[idx] = True

    for i in graph[idx]:
        if not visited[i]:
            # DFS는 부모노드에서 자식노드로 탐색을 한다
            # 그러므로 호출된 idx값이 부모노드의 숫자이다
            answer[i] = idx
            DFS(i)

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 0. 입력 및 초기화
N = int(input())
graph = [[]for _ in range(N+1)]
visited = [False] * (N+1)
answer = [0] * (N+1)

# 1. 연결 요소 입력
for _ in range(N-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 2. 오름차순 정렬
for i in range(1, N+1):
    graph[i].sort()

# 3. DFS호출
DFS(1) #idx

# 4. 출력
for i in range(2, N+1):
    print(answer[i])

다른 DFS 문제와 다른 점은 DFS함수 안에서 반복문을 돌리면서 idx번의 리스트 안에서 방문 하지 않은 값을 찾았을때, DFS를 재호출 하기전에 idx값을 answer의 i번에 넣어준다는 것이다. 맨 위에 있는 최상단 노드부터 시작했기 때문에 idx에서 i번을 찾았을때는 idx가 i의 부모 노드라는 뜻이다.