[백준] No.11495 - 격자 0 만들기 (C++, 최대 유량)

문제

 

https://www.acmicpc.net/problem/11495

11495번: 격자 0 만들기

 

풀이

 

solved.ac 난이도: Platium 2

 

그래프 모델링이 필요한 최대 유량 문제.

 

 

문제의 설명에서는 연산을 한 번씩 진행하여 각 정수를 1씩 줄이지만 생각해보면 어떤 정수끼리 짝을 짓는 가는 중요하지 않다.

예제의 입력을 생각해보면 어떤 짝이든 짝지은 두 정수를 최대한 줄여주면 결과는 동일하다.

 

 

여기서 연산을 한번 진행할 때 전체 값의 합은 2씩 줄어드는 것을 확인할 수 있다.

연산은 유량이라고 생각하면 두 짝의 정수에서 최대한의 유량을 흘리면 두 정수가 진행할 수 있는 최대한의 연산을 수행한 것과 같다.

 

이러한 최대 유량 그래프를 구현하기 위해서는 인접한 상하좌우 칸끼리 연결해야 한다.

이를 위해 칸을 다음과 같이 빨간 칸과 파란 칸 두 가지로 분류한다.

 

 

이제 그래프에 3가지 종류의 간선을 생성한다.

(연산 = 유량임을 생각하면서 봐보자.)

 

1. source에서 빨간 칸으로의 간선

빨간 칸은 최대 자신의 정수만큼의 연산을 진행할 수 있으므로 용량은 자신의 정수이다.

 

2. 빨간 칸에서 인접 상하좌우의 파란 칸으로의 간선

빨간 칸에서 파란 칸으로의 용량은 INF로 설정한다.

(sink로의 간선에서 어차피 제한되므로)

 

3. 파란 칸에서 sink로의 간선

파란 칸은 최대 자신의 정수만큼의 연산을 진행할 수 있으므로 용량은 자신의 정수이다.

 

 

 

이런 식으로 바로 자신의 인접 칸과 다른 색으로 만들어주면

source -> u -> v -> sink로의 유일한 경로를 만들어 줄 수 있다.

 

만약에 파란 칸도 빨간 칸으로의 간선을 만든다면

source -> v -> u ->sink로의 경로도 존재하여

동일한 연산이 여러 번 일어나게 된다.

따라서 빨간 칸에서 파란 칸, 혹은 파란 칸에서 빨간 칸으로의 간선 중 하나만 선택하여 그래프를 구현하자.

 

 

이때 두 정수(u, v) 중에 하나가 최대 연산(유량)으로 0(잔여 용량)이 되었다면

더 이상 두 정수를 1씩 줄여줄 수 없으므로 u, v사이에는 유량을 흘릴 수 없다.

따라서 최대 용량을 구한 그래프에서 잔여 용량이 남은 정점은 인접 정점이 연산으로 모두 0이 된 경우이다.

 

그래프의 최대 용량(연산이 진행된 횟수)을 max_flow라고하면, 연산이 한번 진행될 때 전체 값의 합은 2씩 감소하므로 

다음을 구할 수 있다.

전체 값의 합 - (2*최대 용량) = 남은 전체 값의 합 

total_value - (2*max_flow) = remain_value

 

 

 

남은 값들은 인접 칸과 연산을 할 수 없으므로 해당 칸만을 1 감소시키기 위해 연산을 진행해야 한다.

따라서 모든 칸을 0을 만들기 위해서 해야 하는 연산의 횟수는 다음과 같다.

 

max_flow + remain_value = max_flow + total_value - (2*max_flow) 

= total_value - max_flow

 

 

이를 구현하기위해 source는 0, sink는 1 정점으로 설정해주자.

단, 인접 정점의 여부를 단순히 모든 정점의 용량을 검사하는 식으로 구현하면 시간 초과가 발생하므로

해당 정점의 인접 정점만 따로 저장하는 vector<vector<int>>를 이용하여 구현하였다.

 

 

코드