[백준] 11682 Landscaping Python 3

에드몬드-카프 알고리즘을 이용한 최대유량 계산을 위한 클래스로 구성되어 있다. 정점 수는 n 이 주어지며 인접 리스트 self.adj 는 각 정점에 도착하는 간선 정보를 [목적지, 역방향 간선의 인덱스, 잔여 용량] 형태로 저장한다. 경로 복원을 위한 배열 self.par 는 각 정점의 역방향 간선 인덱스를 기록하는 용도로 사용되며, 초기화 시 모든 원소가 -1로 설정된다.

간선 추가는 add_edge 메서드를 통해 수행된다. a에서 b로 가는 용량 cap인 간선과 함께 반대 방향의 간선이 필요하므로, a->b 간선은 목적지와 역방향 인덱스, 용량을 저장하고, b->a 역방향 간선은 반대 방향으로도 정보를 저장한다. 이는 흐름 갱신 시 잔여 용량을 빠르게 업데이트하기 위함이다. 두 간선은 동시에 추가되며, 초기 잔여 용량은 각각 cap 과 rcap 으로 설정된다.

bfs 메서드는 에드몬드-카프 방식의 BFS를 구현한다. s에서 시작하여 용량이 남아 있는 간선만 따라가며 경로를 탐색하고, 도달하는 경로에서 흘릴 수 있는 최대 흐름 값을 반환한다. 경로가 없으면 0을 반환하며, 도착지에 도달하면 즉시 그 흐름 값을 반환한다. 탐색 과정에서 각 정점의 방문 여부를 par 배열로 관리한다.

flow 메서드는 s에서 t로의 최대 유량을 반복적으로 구한다. BFS를 통해 얻은 흐름 f가 0이 될 때까지 순환하며, 각 단계에서 발견한 경로를 따라 역방향 간선의 잔여 용량과 정방향 간선의 잔여 용량을 갱신한다. 경로에서의 흐름은 역방향 간선의 용량을 증가시키고 정방향 간선의 용량을 감소시키는 방식으로 반영된다.

solve 함수는 표준 입력에서 n, m, a, b를 읽고 격자를 구성한 뒤 그래프를 초기화한다. 격자의 각 칸은 노드로 매핑되며 '.'인 칸은 시작 지점 s로부터의 용량 b를, '#'인 칸은 노드에서 싱크로의 용량 b를 각각 연결한다. 또한 상하좌우 인접한 칸 간에는 가중치 a를 가지는 간선을 추가한다. 인접 간선은 양방향으로 연결되며, 각 간선은 잔여 용량을 반영하도록 설정된다. 마지막으로 최대 유량을 출력한다. 코드 전체는 입력 예시를 처리하고 최종적으로 최대 흐름 값을 표준 출력한다.