17412번 도시 왕복하기 1을 풀며 네트워크 플로우 개념 정리

최근 백준 17412번 도시 왕복하기 1 문제를 풀면서 네트워크 플로우의 기본 개념, 특히 정방향/역방향 유량과 잔여 용량의 중요성을 이해하게 되었습니다. 복잡하게 느껴졌던 개념들이 명확해졌고, 이를 바탕으로 코드를 직접 작성해보았습니다.

학습 주제

• 공부 주제: 네트워크 플로우 (Network Flow) 개념 및 알고리즘
• 대화 제목: 17412번 도시 왕복하기 1을 풀며 네트워크 플로우 개념을 정리
• 학습 날짜: 2026년 3월 2일

질문과 탐구

처음 네트워크 플로우를 접했을 때, 특히 정방향 유량, 정방향 잔여 유량, 역방향 유량, 역방향 잔여 유량 이 네 가지 개념이 헷갈렸습니다. 핵심은 "지금 얼마나 보냈는가(Flow)"와 "앞으로 얼마나 더(혹은 덜) 보낼 수 있는가(Residual)"의 차이를 이해하는 것임을 알게 되었습니다.

특히 역방향 잔여 유량이 왜 필요한지, 정방향 유량과 잔여 공간만 알면 되지 않나 하는 의문이 들었습니다. 이미 보낸 유량을 취소하기 위한 '장치'로서의 역방향 개념이 어떻게 전체 최대 유량을 구하는 데 결정적인 역할을 하는지 탐구했습니다.

핵심 학습 내용

• 주요 개념:

  • 정방향 유량 (Forward Flow): 현재 간선을 따라 실제로 흐르는 양 ($f(u,v)$). 용량을 초과할 수 없습니다.
  • 정방향 잔여 유량 (Forward Residual Capacity): 앞으로 더 보낼 수 있는 여유분 ($c(u,v)-f(u,v)$).
  • 역방향 잔여 유량 (Backward Residual Capacity): 이미 보낸 유량을 취소(되돌릴) 수 있는 양 ($f(u,v)$). 이는 실제 물을 반대로 보내는 것이 아니라, 장부상으로 정방향 유량을 깎아내는 효과를 가집니다.

• 중요 포인트:

  • 역방향 잔여 유량은 알고리즘이 잘못된 경로 선택을 했을 때, 유량을 **"상쇄(Cancel)"**하여 다른 더 효율적인 경로를 찾도록 돕는 핵심적인 역할을 합니다.
  • 이를 통해 **"먼저 선점한 놈이 임자"**가 아니라, "나중에 더 좋은 경로가 나오면 먼저 간 놈을 뒤로 물리고 새 길을 뚫어주는" 유연한 탐색이 가능해집니다.
  • BFS(너비 우선 탐색)는 정방향 간선뿐만 아니라 역방향 잔여 유량도 **"갈 수 있는 길(잔여 용량이 0보다 큰)"**로 간주하여 탐색합니다.
  • capacity[u][v] - flow[u][v]라는 단 하나의 식으로 정방향 잔여 용량과 역방향 잔여 유량(취소 티켓)을 모두 계산할 수 있습니다. 역방향 간선 자체의 용량은 0이지만, flow[v][u]가 음수이기 때문에 0 - (-flow[u][v]) = flow[u][v]가 되어 잔여 용량이 양수로 계산됩니다.

• 예시 코드 (17412번 문제 적용):

  • 각 간선의 용량을 1로 설정하여, 한 번 사용된 간선은 더 이상 정방향으로 쓸 수 없게 합니다.
  • adj[v].push_back(u)를 통해 역방향 간선을 "길"로서 등록하여 BFS가 탐색할 수 있게 합니다.
  • BFS를 통해 경로를 찾으면, flow[u][v] += 1 (정방향 유량 증가)과 flow[v][u] -= 1 (역방향 유량 감소, 즉 상쇄)를 동시에 수행합니다.
  • 이 과정을 while(bfs()) 루프 안에서 반복하며, 더 이상 Start에서 Target으로 갈 수 있는 경로가 없을 때(parent[Target] == -1) 종료합니다.

#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; // N: 도시의 수, P: 도로의 수
    cin >> N >> P;

    for (int i = 0; i < P; i++) {
        int u, v;
        cin >> u >> v;
        
        // 1. 정방향과 역방향 모두 길을 열어줌 (BFS가 탐색할 수 있도록)
        adj[u].push_back(v);
        adj[v].push_back(u); 
        
        // 2. 문제 조건: 각 간선은 한 번만 쓸 수 있으므로 용량은 1
        capacity[u][v] = 1; 
    }

    int totalFlow = 0;      // 찾아낸 총 경로의 수 (최대 유량)
    int Start = 1;          // 출발지: 1번 도시
    int Target = 2;         // 도착지: 2번 도시

    // [BFS 무한 반복] 가능한 최대한 많은 서로 다른 경로를 찾기 위해!
    while (true) {
        // 매 pass마다 방문 체크(부모 기록)를 초기화하여 새로운 경로를 발굴할 준비를 함
        // 직전 pass까지 갱신한 간선별 유량은 유지하되, 방문 체크를 초기화함으로써
        // 아직 탐색하지 않았거나, 잔여 유량이 남아있거나, 역방향 취소 티켓을 가진 간선까지 고려하여
        // 시작 지점에서 도착 지점까지 가능한 최대 유량을 얻기 위한 새로운 경로들을 발굴해낸다.
        fill(parent, parent + MAX, -1);
        queue<int> q;
        
        q.push(Start); // 시작점 도시를 큐에 넣고 BFS 시작

        // BFS 탐색: 큐가 비거나 Target에 도달하기 전까지 반복
        while (!q.empty() && parent[Target] == -1) {
            int curr = q.front();
            q.pop();

            for (int next : adj[curr]) {
                // 논리 3: 정방향이든 역방향이든 '잔여 유량'이 있어야만 갈 수 있는 길로 간주함
                // (capacity - flow > 0) 이 조건이 정방향의 벽과 역방향의 기회를 모두 판별함
                // capacity[next][curr]가 0이라도 flow[curr][next]가 음수면 양수가 됨 (역방향 취소 티켓)
                if (capacity[curr][next] - flow[curr][next] > 0 && parent[next] == -1) {
                    q.push(next);
                    parent[next] = curr; // 어디서 왔는지 기록 (경로 역추적용)
                }
            }
        }

        // 논리 1: 큐가 빌 때까지 쑤셔봤는데도 Target에 도달하지 못했다면?
        // 정말로 더 이상 한 방울도 보낼 수 있는 경로가 없다는 뜻이므로 종료 (항복)
        if (parent[Target] == -1) break;

        // 논리 2: 경로를 찾았으므로 '역전파' 느낌으로 장부를 업데이트함
        // 이 과정에서 flow[v][u]를 깎아 미래의 BFS에게 '상쇄/재배치'의 기회를 유도함
        // Target에서 Start로 거슬러 올라가며 경로상의 각 간선에 유량을 1만큼 흘린다.
        for (int i = Target; i != Start; i = parent[i]) {
            int u = parent[i]; // 이전 노드 (Start에서 Target으로 가는 방향 기준)
            int v = i;         // 현재 노드 (Start에서 Target으로 가는 방향 기준)

            flow[u][v] += 1; // 정방향 유량 증가 (내가 이 간선을 썼음을 기록)
            flow[v][u] -= 1; // 역방향 유량 감소 (상쇄/취소 티켓 생성) - 다음 BFS가 고려할 수 있게 함
        }
        
        // 한 번의 BFS 성공 = 하나의 서로 다른 경로를 완벽히 찾아내 물을 흘림
        totalFlow++;
    }

    // 최종적으로 쥐어짜낸 모든 서로 다른 경로의 합 출력
    cout << totalFlow << endl;

    return 0;
}

이해한 내용

• 네트워크 플로우는 단순히 물을 흘려보내는 것을 넘어, 자원을 효율적으로 분배하고 제약 조건 하에서 최대치를 뽑아내는 알고리즘적 사고방식을 담고 있습니다.
• 특히 역방향 간선은 "결정을 되돌릴 수 있는" 강력한 메커니즘을 제공하며, 이를 통해 복잡한 네트워크에서도 최적의 해를 찾아낼 수 있습니다.
• BFS의 반복적인 사용과 parent 배열을 이용한 경로 추적, 그리고 flow 배열을 이용한 유량 업데이트 및 상쇄 과정이 전체 알고리즘의 핵심이라는 것을 알게 되었습니다.

실전 적용

• 적용 가능 분야:
  • 교통 흐름 최적화: 도시 간 도로망에서 차량의 최적 경로 탐색 및 혼잡 최소화.
  • 자원 할당: 여러 사용자에게 제한된 자원(대역폭, 처리 능력 등)을 효율적으로 분배.
  • 네트워크 라우팅: 데이터 패킷을 가장 효율적으로 목적지까지 전달하는 경로 탐색.
  • 배정 문제: 작업자와 작업 간의 연결을 통해 최대 매칭 또는 최소 비용 매칭 찾기 (이분 매칭의 기반).
• 실습 계획:
  • 이번에 학습한 내용을 바탕으로 17412번 외에 백준의 다른 네트워크 플로우 문제들(예: 6086번 최대 유량, 2316번 도시 왕복하기 2)을 풀어보며 다양한 상황에 대한 이해를 높일 계획입니다.
• 응용 아이디어:
  • 각 도시의 '처리 용량'을 제한하는 문제를 만들어보기 (노드 분할 기법을 학습해야 함).
  • 간선마다 '이동 시간'이나 '비용'을 추가하여 최소 비용 최대 유량 문제를 풀어보기.

추가 학습 계획

• 더 깊이 공부하고 싶은 부분:
  • 노드 분할(Node Splitting) 기법: 노드 자체에도 용량 제한이 있는 문제를 해결하기 위해.
  • 최소 비용 최대 유량(Min-Cost Max-Flow, MCMF) 알고리즘: 유량에 비용 개념이 추가된 문제들을 풀기 위해.
  • 디닉(Dinic) 알고리즘: 에드몬드-카프보다 더 효율적인 최대 유량 알고리즘.
• 관련 자료 찾기:
  • 주요 알고리즘 서적 (예: Introduction to Algorithms, Competitive Programmer's Handbook)의 네트워크 플로우 챕터.
  • 온라인 알고리즘 강의 및 튜토리얼.
  • 백준 알고리즘 문제 풀이 커뮤니티의 관련 해설.
• 다음 학습 주제: 노드 분할 기법을 활용한 2316번 도시 왕복하기 2 문제 풀이.

참고 자료

• 문제: 백준 온라인 저지 17412번 도시 왕복하기 1
• 알고리즘: 에드몬드-카프 (Edmonds-Karp) 알고리즘 (BFS 기반 최대 유량 알고리즘)