오늘 문제는,,, 뭔가… 개인적으로 도움이 되는? 문제라고 생각합니다. BFS 알고리즘을 사용하면서 뭔가 구현 능력이 가미되야하는 듯한 느낌이라고할까? 심지어, 영어로 문제가 되어있고, 이걸 문제를 글만보고 이해하는데 좀 힘들었던 문제였습니다.
하지만, 제대로만 이해한다면 알고리즘을 그대로 사용하면 되는 문제였기에 도움이 되는 문제라고 생각합니다.
1. 오늘의 학습 키워드
- 구현
- BFS
- DFS
- graph
- tree
2. 문제: Clear Cold Water (6188번)
- 단계: 🥈실버 2티어
- 알고리즘 분류: 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
- 출처: https://www.acmicpc.net/problem/6188
Clear Cold Water
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 115 | 81 | 70 | 81.395% |
문제
The steamy, sweltering summers of Wisconsin's dairy district stimulate the cows to slake their thirst. Farmer John pipes clear cold water into a set of N (3 <= N <= 99999; N odd) branching pipes conveniently numbered 1..N from a pump located at the barn. As the water flows through the pipes, the summer heat warms it. Bessie wants to find the coldest water so she can enjoy the weather more than any other cow.
She has mapped the entire set of branching pipes and noted that they form a tree with its root at the farm and furthermore that every branch point has exactly two pipes exiting from it. Surprisingly, every pipe is exactly one unit in length; of course, all N pipes connect up in one way or another to the pipe-tree.
Given the map of all the pipe connections, make a list of the distance from the barn for every branching point and endpoint. Bessie will use the list to find the very coldest water.
The endpoint of a pipe, which might enter a branching point or might be a spigot, is named by the pipe's number. The map contains C (1 <= C <= N) connections, each of which specifies three integers: the endpoint E_i (1 <= E_i <= N) of a pipe and two branching pipes B1_i and B2_i (2 <= B1_i <= N; 2 <= B2_i <= N). Pipe number 1 connects to the barn; the distance from its endpoint to the barn is 1.
입력
- Line 1: Two space-separated integers: N and C
- Lines 2..C+1: Line i+1 describes branching point i with three space-separated integers: E_i, B1_i, and B2_i
출력
- Lines 1..N: Line i of the output contains a single integer that is the distance from the barn to the endpoint of pipe i
예제 입력 1
5 2
3 5 4
1 2 3
예제 출력 1
1
2
2
3
3
힌트
The input above describes this pipe map:
+------+
| Barn |
+------+
| 1
*
2 / \ 3
*
4 / \ 5Pipe 1 is always distance 1 from the barn. Pipes 2 and 3 connect directly to pipe 1 and thus are distance 2 from the barn. Pipes 4 and 5, which connect to pipe 3, are distance 3 from the barn.
3. 나의 풀이
문제 분석
참… 오늘 문제는 영어로 되어 있습니다. 한 번 차근차근 분석해볼까요?
문제를 보시면 Farmer John, Bessie 이 두 사람이 나오는데, 이 사람들이 중요한 것은 아닙니다.
N개의 파이프를 헛간으로부터 연결하는데, 이 파이프들이 헛간을 루트로 하는 트리 구조라고 합니다. 또한 트리의 형태는 이진 트리이며, 모든 파이프의 길이는 1이라고 합니다. 즉, 엣지의 길이가 1이라고 생각하면 됩니다.
이 상황에서, 문제가 요구하는 것은 헛간 (루트)에서 모든 노드들과의 거리를 구하는 것입니다. 아! 노드가 의미하는 것은 딱히 나와 있지 않지만 "branching point and endpoint"라고 나와 있어, 편하게 노드라고 부르겠습니다.
결론적으로 파이프(엣지)들이 트리 형태로 연결되어 있으며, 파이프들의 모든 길이는 1입니다. 따라서 루트(헛간)에서 모든 노드들 간의 거리를 출력하는 문제입니다!
참, 영어로 된 문제라서 뭔가 말이 복잡해 이해하는 데 어려울 수 있습니다. 이럴 때는 입력, 출력, 그리고 힌트를 보면 이해가 될 듯합니다.
입력을 보면,
첫 번째 줄에는 두 개의 정수 N과 C가 주어지는데요. N은 파이프 수(엣지 수), C는 트리의 높이, 레벨이라고 보면 될 것 같습니다.
두 번째 줄부터는, 각 C에 있는 루트 노드 E_i와 연결되어 있는 자식 노드 B1_i, B2_i입니다.
하지만 알아야 할 것은 1번 파이프는 무조건 헛간(루트)과 연결된 엣지라고 보면 됩니다.
출력은 각 노드와의 거리를 출력하면 됩니다. 1칸씩 나오는 것을 보면 반복문을 통해 거리를 저장한 변수를 출력하면 될 것 같네요.
접근 방법
문제 분석 결과, 모든 노드들과의 거리를 출력하는 문제이며, 트리 형태로 이뤄졌기 때문에 BFS, DFS 알고리즘을 사용하면 됩니다.
트리는 특별한 형태의 그래프로, 노드들 간의 연결 관계가 계층적이며 사이클이 존재하지 않습니다. 여기서 트리의 루트는 헛간(파이프 1)이며, 나머지 파이프들이 자식 노드처럼 연결되어 있습니다.
1. 트리 구조의 특성
- 트리는 사이클이 없는 연결 그래프입니다. 모든 노드(여기서는 파이프)는 하나의 루트(헛간)에서 출발하여 다른 노드(파이프)까지 단 하나의 경로만 존재합니다.
- 이 특성 덕분에 어떤 노드에서 다른 노드까지의 최단 거리는 단순히 그 경로의 길이와 같습니다.
2. BFS (너비 우선 탐색)
- BFS는 가까운 노드부터 탐색해나가는 방식입니다. 루트 노드에서 시작해 가장 가까운 노드들을 먼저 방문하고, 그다음으로 멀리 있는 노드를 방문합니다.
- BFS는 최단 경로 문제를 해결하는 데 매우 적합합니다. 각 단계에서 현재 노드의 자식 노드(즉, 연결된 파이프)를 방문하며 거리를 하나씩 더해 나가므로, 방문한 노드까지의 거리는 항상 최단 거리입니다.
- 이 문제에서는 BFS를 사용하여 루트(헛간)에서 모든 노드(파이프)까지의 거리를 정확히 계산할 수 있습니다.
3. DFS (깊이 우선 탐색)
- DFS는 한 경로를 끝까지 탐색한 후, 다음 경로로 이동하는 방식입니다. 즉, 루트에서 시작해 가능한 한 깊이 들어가서 탐색하다가 더 이상 깊이 갈 수 없으면 다시 돌아와 다른 경로로 탐색합니다.
- 트리에서는 루트에서 시작해 특정 노드까지 도달하는 유일한 경로가 존재하기 때문에, DFS로도 각 노드까지의 거리를 정확히 계산할 수 있습니다. DFS에서 노드를 방문할 때마다 현재까지의 경로 길이를 기록하면, 해당 노드까지의 최단 거리를 얻을 수 있습니다.
- 스택(명시적 스택 또는 재귀 호출)을 사용한 DFS는 트리의 모든 노드를 방문하면서 각 노드까지의 거리를 효과적으로 계산할 수 있습니다.
4. 문제에서 DFS, BFS를 사용할 수 있는 이유
- 유일한 경로: 트리 구조의 특성상 루트에서 다른 모든 노드까지의 경로는 유일하므로, DFS나 BFS를 통해 해당 경로의 길이를 구하는 것이 가능하며 정확합니다.
- 거리 계산: BFS는 너비 우선 탐색으로 최단 거리(루트에서 노드까지의 거리)를 구하기에 이상적이며, DFS 역시 각 경로를 따라가며 거리 계산이 가능하므로 적합합니다.
그럼, 이제 코드를 살펴볼까요?
아래는 문제를 해결하는 코드에 대한 설명입니다.
4. 코드 설명
BFS (너비 우선 탐색) 코드 설명
우선, BFS(너비 우선 탐색) 알고리즘을 사용하여 문제를 해결하는 방법을 설명합니다. BFS는 주로 최단 경로를 찾는 문제에서 사용되며, 트리 구조에서 루트에서 다른 모든 노드까지의 거리를 구하는 데 적합합니다.
from collections import deque, defaultdict
import sys
def calculate_distances_bfs(N, C, connections):
# 트리를 나타내는 인접 리스트
tree = defaultdict(list)
# 트리 구조를 만듭니다
for E, B1, B2 in connections:
tree[E].append(B1)
tree[E].append(B2)
# 각 파이프의 거리를 저장할 리스트, 초기값은 -1로 설정
distances = [-1] * (N + 1)
# BFS를 사용하여 헛간(파이프 1)에서 각 파이프까지의 거리를 계산
queue = deque([1])
distances[1] = 1 # 루트에서 루트로의 거리는 1
while queue:
current_pipe = queue.popleft()
current_distance = distances[current_pipe]
for neighbor in tree[current_pipe]:
if distances[neighbor] == -1: # 아직 방문하지 않은 경우
distances[neighbor] = current_distance + 1
queue.append(neighbor)
# 결과 출력
for i in range(1, N + 1):
print(distances[i])
N, C = map(int,sys.stdin.readline().split())
connections = [tuple(map(int, sys.stdin.readline().split())) for _ in range(C)]
calculate_distances(N,C,connections)
코드 구조와 동작 원리
- 트리 구조 생성:
- 입력으로 주어진 파이프 연결 정보를 바탕으로 트리 구조를 만듭니다.
defaultdict(list)를 사용해 각 파이프의 자식 파이프를 저장합니다.
- 입력으로 주어진 파이프 연결 정보를 바탕으로 트리 구조를 만듭니다.
- BFS 탐색:
- BFS 탐색은 큐(
deque)를 이용하여 구현됩니다. 헛간(파이프 1)을 시작점으로 하고, 큐에 현재 노드와 그 노드까지의 거리를 저장합니다. - 큐에서 노드를 하나씩 꺼내어 그 노드와 연결된 자식 노드들을 모두 방문합니다. 이때 자식 노드까지의 거리는 부모 노드까지의 거리보다 1만큼 더 깁니다.
- 이미 방문한 노드는 큐에 추가하지 않음으로써, 중복 방문을 방지합니다.
- BFS 탐색은 큐(
- 거리 출력:
- BFS가 완료되면
distances리스트에는 헛간으로부터 각 파이프까지의 거리가 저장됩니다. 이 거리를 차례대로 출력합니다.
- BFS가 완료되면
DFS (깊이 우선 탐색) 코드 설명
다음으로, DFS(깊이 우선 탐색)를 사용하여 문제를 해결하는 방법을 설명합니다. DFS는 한 경로를 끝까지 탐색한 후, 다음 경로를 탐색하는 방식으로 진행됩니다.
DFS는 재귀적으로 구현할 수 있지만, 여기서는 명시적인 스택을 사용해 구현합니다.
from collections import defaultdict,deque
import sys
def calculate_distances_dfs_stack(N, C, connections):
# 트리를 나타내는 인접 리스트
tree = defaultdict(list)
# 트리 구조를 만듭니다
for E, B1, B2 in connections:
tree[E].append(B1)
tree[E].append(B2)
# 각 파이프의 거리를 저장할 리스트, 초기값은 -1로 설정
distances = [-1] * (N + 1)
# 스택을 사용한 DFS 구현, 거리를 별도로 관리
stack = deque([1]) # 파이프 번호만 저장
distances[1] = 1 # 루트에서 루트로의 거리는 1
while stack:
current_pipe = stack.pop()
current_distance = distances[current_pipe]
# 자식 파이프들을 스택에 추가 (방문하지 않은 경우)
for neighbor in tree[current_pipe]:
if distances[neighbor] == -1: # 아직 방문하지 않은 경우
stack.append(neighbor)
distances[neighbor] = current_distance + 1 # 자식 노드의 거리 계산
# 결과 출력
for i in range(1, N + 1):
print(distances[i])
# 입력을 받아서 처리
import sys
N, C = map(int, sys.stdin.readline().split())
connections = [tuple(map(int, sys.stdin.readline().split())) for _ in range(C)]
calculate_distances_dfs_stack(N, C, connections)
코드 구조와 동작 원리
- 트리 구조 생성:
- BFS와 마찬가지로 입력으로 주어진 파이프 연결 정보를 바탕으로 트리 구조를 만듭니다.
- 스택을 사용한 DFS 탐색:
- DFS는 명시적인 스택을 사용해 구현됩니다. 시작점인 헛간(파이프 1)부터 시작하여 자식 노드들을 스택에 추가합니다.
- 스택에서 노드를 하나씩 꺼내어 그 노드에 해당하는 거리를 계산하고, 자식 노드들을 스택에 추가하여 탐색을 진행합니다.
- 스택이 비워질 때까지 이 과정을 반복합니다.
- 거리 출력:
- DFS가 완료되면
distances리스트에는 헛간으로부터 각 파이프까지의 거리가 저장됩니다. 이 거리를 차례대로 출력합니다.
- DFS가 완료되면
DFS (재귀적) 코드 설명
다음은 재귀적으로 DFS를 구현한 코드입니다. 이 방식은 함수 호출 스택을 이용해 트리의 각 노드를 방문하면서 거리를 계산합니다.
from collections import defaultdict
import sys
def calculate_distances_dfs_recursive(N, C, connections):
# 트리를 나타내는 인접 리스트
tree = defaultdict(list)
# 트리 구조를 만듭니다
for E, B1, B2 in connections:
tree[E].append(B1)
tree[E].append(B2)
# 각 파이프의 거리를 저장할 리스트, 초기값은 -1로 설정
distances = [-1] * (N + 1)
# 재귀적으로 DFS 구현
def dfs(pipe, distance):
distances[pipe] = distance
for neighbor in tree[pipe]:
if distances[neighbor] == -1: # 아직 방문하지 않은 경우
dfs(neighbor, distance + 1)
# DFS 시작: 파이프 1에서 출발 (헛간)
dfs(1, 1)
# 결과 출력
for i in range(1, N + 1):
print(distances[i])
# 입력을 받아서 처리
N, C = map(int,sys.stdin.readline().split())
connections = [tuple(map(int, sys.stdin.readline().split())) for _ in range(C)]
calculate_distances_dfs_stack(N,C,connections)
코드 구조와 동작 원리
- 트리 구조 생성:
- 앞선 BFS와 스택 기반 DFS와 마찬가지로, 입력으로 주어진 파이프 연결 정보를 바탕으로 트리 구조를 만듭니다.
- 재귀적 DFS 탐색:
dfs함수는 현재 노드(파이프)와 그 노드까지의 거리를 인자로 받아, 해당 노드에 대한 거리를 설정합니다.- 그런 다음, 해당 노드에 연결된 자식 노드들을 재귀적으로 호출하여 자식 노드까지의 거리를 계산합니다.
- 이 과정에서 아직 방문하지 않은 자식 노드만을 대상으로 재귀 호출을 진행하여, 모든 노드를 방문합니다.
- 거리 출력:
- DFS가 완료되면
distances리스트에 헛간으로부터 각 파이프까지의 거리가 저장됩니다. 이 거리를 차례대로 출력합니다.
- DFS가 완료되면
종합
이제 우리는 BFS, 스택 기반 DFS, 그리고 재귀적 DFS를 통해 문제를 해결하는 세 가지 방법을 살펴보았습니다. 각각의 방법은 문제의 성격과 개인적인 선호에 따라 선택할 수 있으며, 트리 구조의 특성상 이 문제에서는 모두 올바른 결과를 도출할 수 있습니다.
- BFS는 최단 거리 계산에 직관적이고 적합합니다.
- 스택 기반 DFS는 명시적인 스택을 사용하여 DFS의 진행을 관리합니다.
- 재귀적 DFS는 간결하고 직관적인 코드로 깊이 우선 탐색을 수행합니다.
이러한 다양한 방법을 이해하고 사용할 수 있다면, 다양한 문제에서 더 유연하게 접근할 수 있습니다.
세 가지의 코드 수행 결과 모두 통과했습니다!
전체 코드는 저의 깃허브를 가시면 보실 수 있습니다.
5. 결론
이 문제는 이해를 제대로 하면 DFS, BFS를 쉽게 적용할 수있는 문제입니다. 하지만 문제 이해를 못한다면 산으로 갈 수 있는 문제기도 한데요.
문제의 글을 봤을 때 이해하기 힘들때는 입력과 출력, 예시를 보는게 훨씬 효과적이라는 것을 알려준 문제라는 생각이 듭니다.
질문은 언제나 환영입니다!! 도움이 되셨다면 좋아요, 팔로우도 꼭 부탁드립니다.
읽어주셔서 감사합니다!
