[백준] 12670 The Year of Code Jam (Large) Python 3

다음 내용은 그래프 이론의 최대 유량 문제를 풀기 위한 Dinic 알고리즘의 구현 및 이를 이용한 그리드 문제 해결 흐름을 요약한다. 먼저 Dinic 클래스는 정점 수 n에 대해 인접 리스트 adj를 가지며, 간선 추가는 add_edge로 수행된다. 방향 간선의 용량은 cap이며, 역방향 간선의 용량은 is_directed 매개변수에 따라 달라진다. 양방향 간선인 경우 역방향 간선의 초기 용량이 cap으로 설정된다. 이를 통해 방향성 여부를 쉽게 조정한다.

레벨 그래프 구성은 bfs로 수행되며, 시작점 s에서 각 정점까지의 최단 간선 수를 level 배열에 기록한다. 잔여 용량이 양수이고 아직 방문되지 않은 정점만 탐색하여 레벨 그래프를 만든다. 레벨 그래프가 구성되면, dfs 형식의 함수인 send_flow를 통해 차단 흐름(blocking flow)을 찾는다. 현재 노드에서 다음 노드로 보낼 수 있는 잔여 용량과 레벨 차이를 고려해 재귀적으로 흐름을 흘려보낸다. 흐름이 도달하면 정방향 간선의 잔여 용량을 감소시키고 역방향 간선의 잔여 용량을 증가시킨다. 이 과정을 더 이상 흐름을 보낼 수 없을 때까지 반복해 최대 유량을 구한다.

solve_one_case 함수는 격자 문제를 그래프 문제로 변환하는 핵심 로직을 담고 있다. 격자의 각 칸은 인덱스화되어 노드가 된다. 상하좌우 인접한 칸 사이에는 용량 1의 양방향 간선을 추가한다. 칸의 문자에 따라 특정 노드와 소스 또는 싱크 간의 간선이 부여되는데, 로직은 XOR 연산으로 '.'와 흑백 배치의 패러티를 고려하여 s에서 노드로의 간선이나 노드에서 t로의 간선을 연결한다. ? 문자는 결정되지 않음을 나타내므로 간선 연결에서 제외된다. 최종적으로 s에서 t로의 최대 유량 max_f를 구한 뒤, 전체 가능한 용량 식으로 최종 해를 2*n*m - n - m - max_f 형태로 산출한다.

주요 흐름은 입력으로 주어진 여러 테스트 케이스에 대해 각 케이스마다 격자 크기와 내용을 패딩 없이 처리하는 대신 주어진 n+2, m+2의 패딩된 그리드를 내부적으로 사용한다는 점이다. 입력 행마다 문자열을 읽어 패딩된 격자에 반영하고 solve_one_case를 통해 해를 계산한 뒤, 각 케이스의 형식에 맞춰 결과를 출력한다. 전체 알고리즘은 Dinic의 구현과 그래프 구성 로직이 결합되어 최대 유량으로부터 문제의 해를 도출하는 흐름을 지닌다.