[BOJ][Python] 백준 4445번 - Tile Cut

문제 풀이

최대 유량

 

문제는 단순하다. 격자판에서 WIN을 총 몇 개 만들 수 있는지 구하는 것인데, S -> W를 연결하고, N -> T에 연결한 다음에 I의 경우에는 W -> I, I -> N을 연결하면 된다. 하지만 이렇게만 하면 틀린다. I는 단 한 개 사용해야 하기 때문이다.

이런 경우가 바로 틀리게 되는 원인인데, I는 1개 밖에 없지만 WIN을 2개 만들 수 있기 때문이다. 이를 방지하기 위해서는 간단하게 I에 대해 정점 분할을 해서 단 한 개의 I에만 유량을 흘리게 하면 된다. 여담으로 이 문제의 입력이 좀 귀찮은 편이다.

 

코드