BOJ 11725번 : 트리의 부모 찾기 (Python/Silver 2)

11725번: 트리의 부모 찾기

---

설명

노드 개수를 7개라고 가정하자. 

예제 입력에 둘째 줄부터 트리 상에서 연결된 두 정점이 주어진다고 했으니 그림으로 표현하면 다음과 같다.

파란색 숫자는 예제에 입력된 두 정점을 순서대로 연결된 것을 표현한 것이다. 

 

풀이

이 문제는 DFS와 BFS 문제로 풀 수 있는데 필자는 DFS로 풀었다.

for _ in range(N-1):
    a, b = map(int, input().split())
    #노드와 연결된 걸 표현하기 위해 인접 리스트에 각각 저장
    graph[a].append(b)
    graph[b].append(a)

 

위 코드를 표현한 것이 우측 사진이다. 인접리스트를 생성해주고, 입력받은 두 정점을 서로 저장한다.

 

 

다음은 dfs를 구현한 것이다.

def dfs(x):
    for i in graph[x]: 
        if visited[i] == 0: #만약 해당 노드에 방문하지 않았다면
            visited[i] = x #해당 노드에 정점을 저장
            dfs(i) #그리고 해당 노드를 재귀

이해하기 어렵다면 아래의 코드를 봐보자. 실제 값을 넣고 설명한 것이다.

def dfs(1):
    for i in graph[1]:      #i = 6, 4 (6부터 탐색)
        if visited[6] == 0: #방문하지 않았으니 현재 0이다.
            visited[6] = 1  #6번은 1번과 연결 돼 있다고 저장
            dfs(6)          #6으로 dfs 탐색
                                ↓
 def dfs(6):
    for i in graph[6]:      # i = 1, 3
        if visited[1] == 0: #방문하지 않았으니 현재 0이다.
            visited[1] = 6  #1번은 6번과 연결 돼 있다고 저장
            dfs(1)          #1로 dfs 탐색
                                ↓
 def dfs(1):
    for i in graph[1]:      # i = 6, 4
        if visited[4] == 0: #6은 위에서 1로 저장돼 있어서 방문하지 않은 4번 확인
            visited[4] = 1  #4번은 1번과 연결 돼 있다고 저장
            dfs(4)          #4로 dfs 탐색
                                .
                                .
                                .

인접 리스트를 계속 방문해 가면서 부모 노드를 저장하는 것을 볼 수 있다. 방문하지 않은 것은 조건문에서 부모 노드를 저장하면서 방문 표시를 한다. 다음은 코드 전체이다.

 

※ 주의할 점

이 문제에서 주의할 것은 반복제한이다. 반복이 기본적으로 1000회로 되어 있어서 sys.setrecursionlimit(10**9) 코드를 추가해서 반복제한을 늘려줘야 한다.

Solution

import sys
input = sys.stdin.readline #입력을 빠르게 하기 위함
sys.setrecursionlimit(10**9) #런타임 에러 나서 추가

N = int(input()) #노드 개수
graph = [[] for _ in range(N+1)] #인접리스트 생성
visited = [0]*(N+1) #방문확인

#DFS 구현
def dfs(x):
    for i in graph[x]: 
        if visited[i] == 0: #만약 해당 노드에 방문하지 않았다면
            visited[i] = x #해당 노드에 정점을 저장
            dfs(i) #그리고 재귀

for _ in range(N-1):
    a, b = map(int, input().split())
    #노드와 연결된 걸 표현하기 위해 인접 리스트에 각각 저장
    graph[a].append(b)
    graph[b].append(a)

dfs(1)

#2번 리스트부터 답 출력
for i in range(2, N+1):
    print(visited[i])