문제링크
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 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번 노드를 루트 노드로 정합니다.
- 6번 노드는 1번 노드와 연결되어 있으므로, 6번 노드의 부모는 1번 노드입니다.
- 3번 노드는 6번 노드와 연결되어 있으므로, 3번 노드의 부모는 6번 노드입니다.
- 이런 식으로 트리의 각 노드를 탐색하면서 부모를 찾아나가면 됩니다.
코드로 풀어보기
이 문제는 트리 탐색 문제이므로 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개의 노드가 있을때 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번 노드까지의 부모 노드를 출