[BOJ 11495] 격자 0 만들기

문제 출처 : https://www.acmicpc.net/problem/11495

11495번: 격자 0 만들기

 

풀이 :

 

네트워크 플로우 최대 유량 문제입니다.

 

아래의 그림처럼 격자를 체스판처럼 나눠서 

Source -> 빨간색 영역 -> 사방의 하얀색 영역 -> Sink

이런식으로 모델링 해 주시면 가로 세로 블럭에 대한 모델링은 완성입니다.

 

 

그 다음 최소 연산 횟수를 구해야 하는데

위의 모델링으로 구할 수 있는 연산 횟수는 

" 둘다 양수인 격자에 대한 최소 연산 횟수 " 입니다.

따라서 양수와 0이 묶인 격자에 대한 처리는 하지 않은 상태입니다.

이에 대한 추가 연산을 해주어야하는데

 

Maximum Flow 를 F라 두었을때,

전체 격자판의 합 sum 에서 2F를 빼면 양수와 0이 묶인 격자에 대한 연산횟수만 남게됩니다.

 

예를 들면

 

1 1 1

1 0 1

 

인 격자판에서의 최대 유량은 2가 될것입니다.

sum - 2F = 1

따라서 0과 정수가 묶인 격자에 대한 연산횟수는 1이 됩니다.

 

0과 정수가 묶인 격자에 대한 연산횟수를 X라 두었을때, 위의 식을 고쳐 쓰면

sum - 2F = X

sum - F = X + F

가 됩니다.

 

따라서 격자를 0으로 만들기 위한 최소 연산 횟수는 전체 격자판의 합(sum) - MaximumFlow(F) 가 됩니다.