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

문제링크

이미지 클릭시 이동

문제링크

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 & 출력

 

 

문제 이해하기

이 문제는 트리에서 각 노드의 부모를 찾는 문제입니다. 트리에서 각 노드는 하나의 부모와 연결되어 있으며, 루트 노드(최 상위 노드)는 부모가 없습니다. 1번 노드를 루트로 설정하고, 나머지 노드들의 부모를 찾아 출력해야 합니다.

 

문제의 입력 형식 이해하기

첫 번째 줄에는 노드의 개수 N이 주어집니다. 트리에는 N개의 노드가 있으며, 두 번째 줄부터 N-1개의 간선 정보가 주어집니다.

예를 들어, 1 6이라는 입력은 노드 1과 노드 6이 서로 연결되어 있다는 의미입니다.

 

예제 입력

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

위 예시에서 첫 번째 줄은 노드의 개수 7개, 두 번째 줄부터는 트리의 간선 정보를 나타냅니다:

• 노드 1과 노드 6이 연결되어 있음.
• 노드 6과 노드 3이 연결되어 있음.
• 노드 3과 노드 5가 연결되어 있음.
• 노드 4와 노드 1이 연결되어 있음.
• 노드 2와 노드 4가 연결되어 있음.
• 노드 4와 노드 7이 연결되어 있음.

 

이 문제에서 트리의 방향은 상관없다.

트리를 이해하기 어려운 경우가 많아서, 트리를 시각화해 보았습니다.

트리 구조는 방향(왼쪽 또는 오른쪽)과 상관없이 형성됩니다.

 

첫 번째 입력 예시에서, 입력받은 노드의 개수는 총 7개로, 트리에는 7개의 노드가 존재합니다. 그리고 두 번째 줄부터는 주어진 간선 정보를 통해 트리의 구조가 완성됩니다.

 

 

문제를 풀기 위해 해야 할 일

문제의 내용을 살펴보면 1번 노드를 루트 노드로 하여, 각 노드의 부모를 찾아야 합니다.

1. 1번 노드를 루트 노드로 정합니다.
2. 6번 노드는 1번 노드와 연결되어 있으므로, 6번 노드의 부모는 1번 노드입니다.
3. 3번 노드는 6번 노드와 연결되어 있으므로, 3번 노드의 부모는 6번 노드입니다.
4. 이런 식으로 트리의 각 노드를 탐색하면서 부모를 찾아나가면 됩니다.

 

코드로 풀어보기

이 문제는 트리 탐색 문제이므로 DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용할 수 있습니다. 이번에는 DFS 방식을 사용하여 문제를 해결해 보겠습니다.

 

BFS와 DFS의 차이

• DFS(깊이 우선 탐색): 한 경로로 끝까지 탐색한 후, 막히면 다시 돌아와 다른 경로를 탐색하는 방식입니다.
• BFS(너비 우선 탐색): 현재 노드와 연결된 모든 노드를 먼저 탐색한 후, 그다음으로 자식 노드들을 탐색합니다.

이번 문제에서는 DFS방식을 사용하여 문제를 풀어보겠습니다.

 

 

노드 연결관계를 저장할 리스트 생성

# 입력 받기
N = int(input())  # 노드의 개수
graph = [[] for _ in range(N+1)]  # 그래프를 초기화, 각 노드의 연결 관계를 저장할 리스트

여기서, N은 노드의 개수이며, graph는 각 노드의 인접 노드들을 저장할 리스트입니다.

문제를 살펴보면 노드 번호는 1번부터 시작하기 때문에, 리스트의 인덱스를 1번부터 사용할 수 있도록 크기를 N+1로 설정합니다.(파이썬의 인덱스는 0번부터 사용하기 때문)

 

N = 5 일 때 graph 리스트의 결과는 아래와 같이 생성됩니다.  

print(graph)  # 결과: [[], [], [], [], [], []]

• graph[0]: 사용하지 않음 (노드 번호는 1부터 시작하니까)
• graph[1]: 1번 노드와 연결된 노드들을 저장하는 빈 리스트
• graph[2]: 2번 노드와 연결된 노드들을 저장하는 빈 리스트
• graph[3]: 3번 노드와 연결된 노드들을 저장하는 빈 리스트
• graph[4]: 4번 노드와 연결된 노드들을 저장하는 빈 리스트
• graph[5]: 5번 노드와 연결된 노드들을 저장하는 빈 리스트

 

간선 정보 입력받기

다음으로 문제 입력의 두 번째 줄부터 입력되는 노드들의 간성정보를 입력받아야합니다.

 

1 2
1 3
2 4
2 5

이 입력을 살펴보면:

• 1번 노드와 2번 노드가 연결되어 있고,
• 1번 노드와 3번 노드가 연결되어 있고,
• 2번 노드와 4번 노드가 연결되어 있고,
• 2번 노드와 5번 노드가 연결되어 있다는 의미입니다.

이 내용을 바탕으로 grpah 변수에 저장됩니다.

 

트리는 항상 N-1개의 간선정보를 가진다.

이때 간선 정보는 N-1개의 줄로 주어집니다. 왜냐하면 트리에는 항상 N개의 노드가 있을때 N-1개의 간선이 있습니다. 위의 이미지를 살펴보면 N은 노드의개수 7를 나타내고 실제 간선은 N-1개의 6개의 간선으로 이루어져있는걸 확인할 수 있습니다.

 

 

간선정보 입력 받기 코드

for _ in range(N-1):  # 트리는 항상 N-1개의 간선을 가집니다.
    a, b = map(int, input().split())  # 두 노드 a와 b가 연결되어 있음
    graph[a].append(b)  # a번 노드에 b번 노드를 연결
    graph[b].append(a)  # b번 노드에도 a번 노드를 연결 (양방향 연결이므로)

for _ in range(N-1): N개의 노드가 있을 때, 트리는 항상 N-1개의 간선을 가집니다. 따라서 N-1번 반복해서 간선 정보를 입력받습니다.

a, b = map(int, input().split()): 두 노드 a와 b가 연결되어 있다는 정보를 입력받습니다.

graph[a].append(b): a번 노드에 b번 노드가 연결되어 있다고 저장합니다.

graph[b].append(a): b번 노드에도 a번 노드가 연결되어 있다고 저장합니다. 트리는 양방향 연결이므로, 두 방향으로 모두 연결해줘야 합니다.

 

 

예시를 통해 이해해보기

5
1 2
1 3
2 4
2 5

예시 입력으로 위와 같은 입력이 주어졌다고 가정해보겠습니다. 여기서 N = 5이므로 트리에는 5개의 노드가 있고 , 4개의 간선정보가 주어졌습니다.

 

graph변수에 아래와 같은 형태로 저장됩니다.

• 노드 1과 2가 연결: graph[1]에 2를 추가하고, graph[2]에 1을 추가합니다.
• 노드 1과 3이 연결: graph[1]에 3을 추가하고, graph[3]에 1을 추가합니다.
• 노드 2와 4가 연결: graph[2]에 4를 추가하고, graph[4]에 2를 추가합니다.
• 노드 2와 5가 연결: graph[2]에 5를 추가하고, graph[5]에 2를 추가합니다.

 

저장된 grpah 구조

graph = [
    [],         # graph[0]은 사용하지 않음
    [2, 3],     # graph[1]: 1번 노드는 2번과 3번 노드에 연결
    [1, 4, 5],  # graph[2]: 2번 노드는 1번, 4번, 5번 노드에 연결
    [1],        # graph[3]: 3번 노드는 1번 노드에 연결
    [2],        # graph[4]: 4번 노드는 2번 노드에 연결
    [2]         # graph[5]: 5번 노드는 2번 노드에 연결
]

최종적으로 grpah리스트를 출력한 결과입니다.

 

DFS깊이 우선 탐색방법

앞에서 DFS와 BFS에대해서 간략하게만 설명했는데 DFS에대해서 조금더 자세히 알고 넘어가보겠습니다.

DFS는 트리나 그래프를 탐색하는 방법 중 하나로, 한쪽 방향으로 끝까지 탐색한 후 다시 돌아와 다른 경로를 탐색하는 방식입니다. 말 그대로 깊이 우선으로 탐색을 진행합니다.

 

이 문제에서는 1번 노드를 루트 노드로 하고, 각 노드의 부모가 누군지 찾는게 목표입니다. DFS를 사용하면 트리의 자식 노드까지 탐색하면서 부모 노드를 기록할 수 있습니다.

 

DFS로 부모찾기

트리 구조에서는 자식 노드들이 부모 노드와 연결되어 있습니다. 따라서 1번 노드를 루트 노드로 하여 DFS를 통해 트리를 탐색하면서 각 노드의 부모를 찾아 기록할 수 있습니다.

 

DFS 함수 구현하기

dfs함수가 어떻게 동작하는지 살펴보겠습니다.

• dfs(첫번째 노드)로 호출하면, 첫번째 부모 노드와 연결된 다른 노드들을 탐색합니다.
• 방문하지 않은 노드가 있으면 그 노드의 부모를 현재 노드로 기록하고, 그 노드에 대해 다시 dfs를 호출해 그 자식 노드들을 탐색합니다.

 

DFS 코드 구조

DFS는 재귀 함수로 구현할 수 있습니다. 트리의 각 노드를 방문할 때마다 그 노드의 부모를 기록하고, 자식 노드를 탐색하는 방식입니다.

여기서 재귀 호출이란, 함수가 자기 자신을 호출해서 문제를 풀어가는 방식입니다.

# 부모 정보를 저장할 배열
visited = [0] * (N + 1)  # 각 노드가 방문되었는지 여부와 부모 정보를 기록할 리스트

def dfs(node):
    # 현재 노드와 연결된 모든 노드를 탐색합니다.
    for neighbor in graph[node]:
        if visited[neighbor] == 0:  # 만약 방문하지 않은 노드라면
            visited[neighbor] = node  # 그 노드의 부모를 현재 노드로 기록
            dfs(neighbor)  # 재귀적으로 그 자식 노드에 대해 다시 DFS 실행


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

위 코드에서는 부모 정보를 저장할 [0]으로 초기화되어있는 리스트 visited를 N+1개를 생성하고, dfs함수에서는 자기자신을 재귀적으로 호출하여 자식노드를 계속 탐색하며 더이상 방문할 자식 노드가 없을때 재귀호출이 종료됩니다.

 

여기서 빈 리스트를 N+1개를 생성하는 이유는 문제에서 노드 번호는 1번부터 시작한다고 하였고, 파이썬의 리스트 인덱스는 0부터 시작하기 때문에 1부터 N번 노드까지 방문하려면 N+1개의 리스트가 필요합니다.

 

 

dfs(현재 노드): 현재 노드를 기준으로 인접한 노드를 탐색합니다

• if visited[neighbor] == 0: 인접한 노드가 아직 방문되지 않았으면, 그 노드를 방문하고 부모를 기록합니다.
• visited[neighbor] = node: 자식 노드(neighbor)의 부모는 현재 노드(node)라고 기록합니다.
• dfs(neighbor): 자식 노드에 대해 재귀적으로 탐색을 이어갑니다.

 

DFS함수 작동 원리

#예시 입력
5
1 2
1 3
2 4
2 5


#graph구조
graph = [
    [],        # graph[0]은 사용하지 않음
    [2, 3],    # 1번 노드는 2번과 3번 노드와 연결됨
    [1, 4, 5], # 2번 노드는 1번, 4번, 5번과 연결됨
    [1],       # 3번 노드는 1번과 연결됨
    [2],       # 4번 노드는 2번과 연결됨
    [2]        # 5번 노드는 2번과 연결됨
]

이번엔 다른 입력값을 통해 graph리스트에 노드들의 간선이 저장되어 있다고 가정해보겠습니다.

 

1. dfs(1)실행 (루트 노드에서 시작)

• 현재 노드: 1번
• 1번 노드는 2번과 3번 노드와 연결되어 있음.
• visited 리스트: [0, 0, 0, 0, 0, 0] (아직 방문하지 않음)
• 1번 노드에서 2번 노드를 탐색 시작.

 

2. dfs(2) 실행 (2번 노드로 이동)

• 현재 노드: 2번
• 2번 노드는 1번, 4번, 5번 노드와 연결되어 있음.
• 1번 노드는 이미 부모로 기록되었으므로 건너뜀.
• visited 리스트: [0, 0, 1, 0, 0, 0] (2번의 부모는 1번)
• 2번 노드에서 4번 노드를 탐색 시작.

 

3. dfs(4) 실행 (4번 노드로 이동)

• 현재 노드: 4번
• 4번 노드는 2번 노드와 연결되어 있음.
• 2번 노드는 이미 부모로 기록되었으므로 건너뜀.
• visited 리스트: [0, 0, 1, 0, 2, 0] (4번의 부모는 2번)
• 4번 노드는 더 이상 자식이 없으므로 탐색 종료.

 

4. dfs(2)로 다시 돌아감 (2번 노드의 나머지 자식 탐색)

• 4번 노드를 탐색 끝냈으니 2번 노드로 돌아옴.
• 이제 5번 노드를 탐색 시작.

 

5. dfs(5) 실행 (5번 노드로 이동)

• 현재 노드: 5번
• 5번 노드는 2번 노드와 연결되어 있음.
• 2번 노드는 이미 부모로 기록되었으므로 건너뜀.
• visited 리스트: [0, 0, 1, 0, 2, 2] (5번의 부모는 2번)
• 5번 노드는 더 이상 자식이 없으므로 탐색 종료.

 

6. dfs(2)로 다시 돌아감 -> dfs(1)로 돌아감

• 5번 노드도 탐색을 끝냈으니 2번 노드로 돌아옴.
• 2번 노드는 이제 자식 노드를 모두 탐색했으니 1번 노드로 돌아감.

 

7. dfs(3) 실행 (3번 노드 탐색 시작)

• 현재 노드: 3번
• 3번 노드는 1번 노드와 연결되어 있음.
• 1번 노드는 이미 부모로 기록되었으므로 건너뜀.
• visited 리스트: [0, 0, 1, 1, 2, 2] (3번의 부모는 1번)
• 3번 노드는 더 이상 자식이 없으므로 탐색 종료.

 

탐색 완료

• 최종 visited 리스트: [0, 0, 1, 1, 2, 2]

 

결과 출력하기

문제에서 각 노드의 부모 노드 번호를 2번째 노드부터 순서대로 출력하라고 명시되어 있기 때문에, 2번째 노드부터 부모를 출력하도록 작성해야합니다.

# 2번 노드부터 부모 출력
for i in range(2, N + 1):
    print(visited[i])  # 2번 노드부터 N번 노드까지의 부모 노드를 출력

 

 

최종적으로 아래와 같은 형태로 각 리스트에 담겨있는 부모 노드를 출력하게 됩니다.

1  # 2번 노드의 부모는 1번
1  # 3번 노드의 부모는 1번
2  # 4번 노드의 부모는 2번
2  # 5번 노드의 부모는 2번

 

 

DFS 전체코드

# 입력 받기
N = int(input())  # 노드의 개수
graph = [[] for _ in range(N+1)]  # 각 노드의 연결 관계를 저장할 리스트

# 간선 정보 입력받기
for _ in range(N-1):  # 트리는 항상 N-1개의 간선을 가집니다.
    a, b = map(int, input().split())  # 두 노드 a와 b가 연결되어 있음
    graph[a].append(b)  # a번 노드에 b번 노드를 연결
    graph[b].append(a)  # b번 노드에도 a번 노드를 연결 (양방향 연결이므로)

# 부모 정보를 저장할 배열
visited = [0] * (N + 1)  # 각 노드가 방문되었는지 여부와 부모 정보를 기록할 리스트

# DFS 함수 정의
def dfs(node):
    for neighbor in graph[node]:
        if visited[neighbor] == 0:  # 방문하지 않은 노드라면
            visited[neighbor] = node  # 부모를 기록 (현재 노드가 부모)
            dfs(neighbor)  # 자식 노드로 이동해 탐색을 이어감

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

# 2번 노드부터 부모 출력
for i in range(2, N + 1):
    print(visited[i])  # 2번 노드부터 N번 노드까지의 부모 노드를 출력

 

 

BFS전체코드

이를 응용해서 BFS코드로 작성하면 메모리를 효율적으로 사용할 수 있고 스택 오버플로우 문제를 피할 수 있습니다.

import sys
from collections import deque

# 입력 받기
input = sys.stdin.read
data = input().splitlines()

N = int(data[0])  # 노드의 개수
graph = [[] for _ in range(N + 1)]  # 각 노드의 연결 관계를 저장할 리스트

# 간선 정보 입력받기
for i in range(1, N):  # 1부터 N-1까지
    a, b = map(int, data[i].split())  # 두 노드 a와 b가 연결되어 있음
    graph[a].append(b)  # a번 노드에 b번 노드를 연결
    graph[b].append(a)  # b번 노드에도 a번 노드를 연결 (양방향 연결)

# 부모 정보를 저장할 배열
visited = [0] * (N + 1)  # 각 노드가 방문되었는지 여부와 부모 정보를 기록할 리스트

# BFS 함수 정의
def bfs(start):
    queue = deque([start])  # 큐 초기화
    visited[start] = -1  # 루트 노드는 부모가 없으므로 -1로 설정

    while queue:
        node = queue.popleft()  # 큐에서 노드를 꺼냄
        for neighbor in graph[node]:  # 현재 노드와 연결된 노드들을 탐색
            if visited[neighbor] == 0:  # 방문하지 않은 노드라면
                visited[neighbor] = node  # 부모를 기록 (현재 노드가 부모)
                queue.append(neighbor)  # 자식 노드를 큐에 추가

# 1번 노드부터 BFS 시작
bfs(1)

# 2번 노드부터 부모 출력
for i in range(2, N + 1):
    print(visited[i])  # 2번 노드부터 N번 노드까지의 부모 노드를 출