백준 17412: 도시 왕복하기 1
/ 16분 분량 / 문제 풀이
백준의 "도시 왕복하기 1" 문제를 풀어보았습니다. 이 문제는 주어진 도시들을 연결하는 경로를 최대한 많이 찾는 문제로, 최대 유량(Maximum Flow) 알고리즘을 활용해야 하는 문제입니다.
백준 17412: 도시 왕복하기 1
백준의 "도시 왕복하기 1" 문제를 풀어보았습니다. 이 문제는 주어진 도시들을 연결하는 경로를 최대한 많이 찾는 문제로, 최대 유량(Maximum Flow) 알고리즘을 활용해야 하는 문제입니다.
1. 문제 소개
- 문제 번호: 17412
- 문제명: 도시 왕복하기 1
- 난이도 (티어): Platinum IV
- 사용 언어: C++
- 실행 시간: 4 ms
- 메모리: 3556 KB
문제 요약:
N개의 도시와 P개의 양방향 도로가 주어집니다. 각 도로는 한 번만 사용할 수 있다는 제약이 있습니다. 1번 도시에서 2번 도시로 가는 서로 다른 경로의 최대 개수를 구하는 문제입니다. "서로 다른 경로"란, 경로를 구성하는 도로의 집합이 서로 다른 경우를 의미합니다.
2. 접근 방법
이 문제는 최대 유량(Maximum Flow) 문제로 접근해야 합니다. 특히, 각 간선(도로)의 용량이 1인 경우에 해당하며, 에드몬즈-카프(Edmonds-Karp) 알고리즘과 같은 최대 유량 알고리즘을 적용할 수 있습니다.
- 알고리즘/자료구조: 최대 유량 알고리즘 (에드몬즈-카프), BFS(너비 우선 탐색), 인접 리스트, 간선 용량 및 유량 관리 배열.
- 선택 이유:
- 문제에서 "각 간선은 한 번만 사용할 수 있다"는 제약은 각 간선의 용량을 1로 설정하는 것과 같습니다.
- "서로 다른 경로의 최대 개수"는 출발지에서 도착지로 흘려보낼 수 있는 최대 유량과 같습니다. 에드몬즈-카프 알고리즘은 BFS를 사용하여 증가 경로(augmenting path)를 찾고 유량을 흘려보내면서 최대 유량을 계산합니다. 각 증가 경로 탐색 시 BFS를 사용하므로, 이 알고리즘이 문제의 요구사항에 부합합니다.
3. 풀이 과정
에드몬즈-카프 알고리즘을 이용하여 최대 유량을 구하는 과정은 다음과 같습니다.
그래프 초기화:
- 각 도시를 노드로, 도로는 간선으로 표현합니다.
- 각 간선의 **용량(capacity)**을 1로 설정합니다. 이는 각 도로를 한 번만 사용할 수 있다는 제약 때문입니다.
- **유량(flow)**은 현재 흐르는 양을 나타내며, 초기에는 모두 0입니다.
- **인접 리스트(adj)**를 사용하여 도시 간의 연결 관계를 저장합니다. 양방향 도로이므로,
u에서v로 가는 도로가 있다면adj[u]에v를,adj[v]에u를 추가합니다.
BFS를 이용한 증가 경로 탐색 (반복):
- 출발지(1번 도시)에서 도착지(2번 도시)까지 잔여 용량이 1 이상인 간선들로만 구성된 경로를 찾습니다. 이 경로를 **증가 경로(augmenting path)**라고 합니다.
- BFS를 사용하여 이 경로를 탐색합니다. BFS 과정에서
parent배열을 사용하여 경로를 역추적할 수 있도록 합니다. - 잔여 용량:
capacity[u][v] - flow[u][v]로 계산됩니다. 이 값이 0보다 커야 해당 간선을 지날 수 있습니다. - 만약 BFS를 통해 도착지(2번 도시)에 도달할 수 있다면, 증가 경로를 찾은 것입니다.
- 만약 BFS가 종료되었는데 도착지에 도달하지 못했다면, 더 이상 보낼 수 있는 경로가 없으므로 알고리즘을 종료합니다.
유량 업데이트:
- 증가 경로를 찾았다면, 해당 경로를 따라 유량을 1만큼 흘려보냅니다.
- 경로 상의 각 간선
(u, v)에 대해:- 정방향 유량
flow[u][v]를 1 증가시킵니다. (즉,capacity[u][v] - flow[u][v]가 1 감소합니다. 이제 이 간선은 정방향으로는 더 이상 지나갈 수 없습니다.) - 역방향 유량
flow[v][u]를 1 감소시킵니다. (이것은 잔차 그래프(residual graph) 개념으로, 나중에 다른 경로에서 이 간선을 역방향으로 사용하여 유량을 상쇄하거나 재배치할 기회를 제공합니다.)
- 정방향 유량
총 유량 누적:
- 하나의 증가 경로를 성공적으로 찾고 유량을 흘려보낼 때마다, 총 유량을 1 증가시킵니다.
종료:
- 더 이상 증가 경로를 찾을 수 없을 때까지 2~4 단계를 반복합니다.
- 최종적으로 계산된 총 유량이 문제에서 요구하는 서로 다른 경로의 최대 개수입니다.
핵심 아이디어
- 간선 용량 1: 각 도로는 한 번만 사용할 수 있으므로, 용량을 1로 설정합니다.
- BFS로 증가 경로 찾기: 잔여 용량이 있는 경로를 BFS로 탐색하여 가장 짧은 증가 경로를 찾습니다.
- 역방향 간선 활용:
flow[v][u] -= 1;연산을 통해 이미 사용된 간선도 다른 경로에서 역방향으로 활용할 수 있게 하여 최대 유량을 찾는 데 기여합니다.
주의할 점
- 인접 리스트 초기화: 양방향 도로이므로
adj[u].push_back(v);와adj[v].push_back(u);를 모두 해주어야 합니다. - 용량과 유량:
capacity는 고정된 값이고,flow는 동적으로 변하는 값입니다.capacity - flow > 0조건을 통해 잔여 용량을 확인해야 합니다. fill(parent, parent + MAX, -1): BFS를 시작할 때마다parent배열을 초기화하여 새로운 경로 탐색이 가능하도록 해야 합니다.
4. 코드 설명
아래는 위에서 설명한 에드몬즈-카프 알고리즘을 C++로 구현한 코드입니다. JSON의 '풀이_코드' 필드 내용을 그대로 가져왔으며, 수정 없이 사용했습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// 도시의 수는 최대 400개 (1번~N번 도시)
const int MAX = 401;
// 장부 기록용 배열들
int capacity[MAX][MAX]; // 통로의 한계치 (용량)
int flow[MAX][MAX]; // 현재 실제로 흐르는 물의 양 (유량)
int parent[MAX]; // 이번 BFS에서 어떤 도시를 거쳐왔는지 기록 (경로 역추적용)
vector<int> adj[MAX]; // 도시들 간의 연결 관계 (인접 리스트)
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, P;
cin >> N >> P;
for (int i = 0; i < P; i++) {
int u, v;
cin >> u >> v;
// 1. 정방향과 역방향 모두 길을 열어줌
// 양방향 도로이므로, 연결 리스트에 양쪽으로 추가합니다.
adj[u].push_back(v);
adj[v].push_back(u);
// 2. 문제 조건: 각 간선은 한 번만 쓸 수 있으므로 용량은 1
// capacity[u][v] = 1; 는 capacity[v][u] = 1; 와 독립적으로 설정됩니다.
// (이는 최대 유량의 원리에 따라, 역방향 간선은 사실상 존재하지 않는다고 보지만,
// 잔차 그래프에서의 유량을 조절하기 위해 필요합니다.)
capacity[u][v] = 1;
}
int totalFlow = 0;
int Start = 1; // 출발지: 1번 도시
int Target = 2; // 도착지: 2번 도시
// [BFS 무한 반복] 가능한 최대한 많은 서로 다른 경로를 찾기 위해!
// 에드몬즈-카프 알고리즘의 핵심으로, 새로운 증가 경로를 계속 찾습니다.
while (true) {
// 매 pass마다 방문 체크(부모 기록)를 초기화하여 새로운 경로를 발굴할 준비를 함
// parent[i] = -1 이면 아직 방문하지 않았다는 뜻입니다.
fill(parent, parent + MAX, -1);
queue<int> q;
q.push(Start);
parent[Start] = Start; // 출발지는 자기 자신을 부모로 하여 BFS 시작 표시
// BFS 수행: 도착지(Target)에 도달할 때까지 큐를 탐색합니다.
while (!q.empty() && parent[Target] == -1) {
int curr = q.front();
q.pop();
// 현재 도시(curr)에서 갈 수 있는 모든 인접 도시(next)를 탐색합니다.
for (int next : adj[curr]) {
// 논리 3: 정방향이든 역방향이든 '잔여 유량'이 있어야만 갈 수 있는 길로 간주함
// (capacity[curr][next] - flow[curr][next]) > 0 조건이 중요합니다.
// 이 조건이 정방향 간선의 잔여 용량을 확인하고,
// 만약 flow[next][curr]가 음수라면 (즉, 역방향 유량이 존재한다면)
// capacity[curr][next] - flow[curr][next] 값이 커지게 되어 역방향 통과 기회를 판별합니다.
if (capacity[curr][next] - flow[curr][next] > 0 && parent[next] == -1) {
q.push(next);
parent[next] = curr; // next 도시의 부모를 curr로 기록하여 경로를 저장합니다.
}
}
}
// 논리 1: 큐가 빌 때까지 쑤셔봤는데도 Target에 도달 못 했다면?
// 즉, parent[Target]이 여전히 -1이라면, 더 이상 보낼 수 있는 경로가 없다는 뜻입니다.
if (parent[Target] == -1) break; // 알고리즘 종료
// 논리 2: 경로를 찾았으므로 '역전파' 느낌으로 장부를 업데이트함
// 찾은 경로를 역추적하면서 유량을 1만큼 흘려보냅니다.
for (int i = Target; i != Start; i = parent[i]) {
int u = parent[i]; // 현재 도시 (경로의 이전 도시)
int v = i; // 다음 도시 (현재 도시로부터 도달한 도시)
// 정방향 유량 증가: u -> v 방향으로 1만큼 흘려보냄.
// 이로 인해 capacity[u][v] - flow[u][v] 값이 1 감소하게 됩니다.
flow[u][v] += 1;
// 역방향 유량 감소: v -> u 방향으로 -1 만큼 흘려보냄.
// 이는 잔차 그래프에서 v->u 간선의 용량을 1 늘리는 효과와 같습니다.
// 즉, 미래의 BFS에서 v->u 경로를 통해 유량을 '돌려보낼' 기회를 제공합니다.
flow[v][u] -= 1;
}
// 한 번의 BFS 성공 = 하나의 경로를 완벽히 찾아내 물을 흘림
// 즉, 하나의 서로 다른 경로를 사용했으므로 총 유량을 1 증가시킵니다.
totalFlow++;
}
// 최종적으로 쥐어짜낸 모든 경로의 합 출력
// 이것이 1번 도시에서 2번 도시로 갈 수 있는 최대 서로 다른 경로의 개수입니다.
cout << totalFlow << endl;
return 0;
}
주요 부분 설명
capacity[MAX][MAX],flow[MAX][MAX]: 각 도시 쌍 간의 통로 용량과 현재 흐르는 유량을 저장하는 2차원 배열입니다.parent[MAX]: BFS 탐색 시 경로를 기록하는 배열입니다.parent[v] = u는u에서v로 왔음을 의미합니다.adj[MAX]: 각 도시에서 연결된 다른 도시들을 저장하는 인접 리스트입니다.while (true)루프: 에드몬즈-카프 알고리즘의 핵심으로, 새로운 증가 경로를 찾을 때까지 반복합니다.fill(parent, parent + MAX, -1): 각 BFS 탐색 전에parent배열을 초기화합니다.capacity[curr][next] - flow[curr][next] > 0: 간선을 따라 이동할 수 있는지 (잔여 용량이 있는지) 확인하는 조건입니다.flow[u][v] += 1; flow[v][u] -= 1;: 증가 경로를 따라 유량을 업데이트하는 부분입니다. 정방향 유량을 늘리고 역방향 유량을 줄이는 것이 중요합니다.totalFlow++: 유효한 증가 경로를 하나 찾을 때마다 총 유량을 1 증가시킵니다.
5. 복잡도 분석
시간 복잡도:
에드몬즈-카프 알고리즘의 시간 복잡도는 일반적으로O(V * E^2)입니다. 여기서V는 정점(도시)의 수,E는 간선(도로)의 수입니다.
하지만 이 문제에서는 각 간선의 용량이 1이고, 최대 유량F가V보다 크지 않으므로, 더 좋은 복잡도인O(F * E)또는O(V * E)로 분석될 수 있습니다.
문제에서N은 최대 400이고,P는 그보다 작으므로O(N * P)또는O(N^2)정도로 볼 수 있으며, 이 정도의 크기에서는 충분히 시간 내에 실행됩니다.공간 복잡도:
capacity,flow배열:O(V^2)(여기서V는 최대 도시 수 401)adj리스트:O(V + E)(여기서E는 도로 수)parent배열:O(V)queue:O(V)
따라서 전체 공간 복잡도는O(V^2)입니다.
6. 배운 점
이 문제를 풀면서 최대 유량 알고리즘, 특히 에드몬즈-카프 알고리즘의 작동 원리를 깊이 이해할 수 있었습니다.
- 최대 유량 문제의 일반화: "서로 다른 경로의 최대 개수"와 같은 문제를 "최대 유량" 문제로 모델링하는 방법을 배웠습니다.
- 잔차 그래프의 중요성: 정방향 간선의 용량을 줄이는 것뿐만 아니라, 역방향 간선의 유량을 조절하여 더 나은 경로를 탐색할 수 있도록 하는 잔차 그래프의 개념을 익혔습니다.
- BFS의 활용: 최대 유량 문제에서 증가 경로를 효율적으로 찾는 데 BFS가 어떻게 사용되는지 알게 되었습니다.
이 문제는 최대 유량 알고리즘을 처음 접하는 사람에게는 다소 어렵게 느껴질 수 있지만, 알고리즘의 흐름을 차근차근 따라가면서 이해한다면 큰 도움이 될 것입니다. 다음에도 더 흥미로운 알고리즘 문제로 돌아오겠습니다!