Cops and Robbers( BOJ 16407 )

문제

16407. Cops and Robbers : https://www.acmicpc.net/problem/16407

16407번: Cops and Robbers

 

문제 파악하기

• 은행에서 도둑들이 탈풀하지 못 하게 바리케이트를 쌓아야 합니다.
• 'B'와 '.'으로 표현된 위치에는 바리케이트를 쌓을 수 없습니다.
• 각각의 좌표값을 정점으로 생각하면 문제를 하나의 그래프로 나타낼 수 있습니다.
• 중간에 바리케이트를 쌓아 도착지점까지 못 가게 만드는 최소 비용은 결국 최소컷을 구해야 한다는 의미입니다.
• 결국 이 문제는 최대유량 최소컷 정리를 활용하는 문제입니다.

 

문제 해결하기

• 각각의 좌표값을 정점으로 하는 하나의 그래프를 만들 수 있습니다.
  출발점 S는 'B'의 위치이며, 도착점 E의 위치는 입력된 정점 범위를 벗어난 모든 경우입니다.
• 좌표값과 좌표값 사이의 용량은 무제한으로 설정하면 됩니다. 좌표값을 이동한다고 비용이 드는 건 아니기 때문입니다.
• 다만 최소컷은 간선을 잘랐을 때 최솟값을 의미하기 때문에 정점 분할 기법이 필요합니다.
  정점을 2개로 나누어 하나의 간선으로 연결하면 그 사이의 간선을 끊어 최소컷을 구할 수 있습니다.
• 나눠진 정점 사이의 용량은 바리케이트 비용을 넣으면 됩니다. 도둑은 정점을 통과할 때에는 그만큼 비용이 들기 때문입니다.
• 간선만 제대로 연결해놓으면 나머지는 간단합니다. 에드먼드-카프 알고리즘을 이용하면 정답을 구할 수 있습니다.
• 물론 도둑을 막을 수 없는 경우를 구하긴 해야합니다. 이 경우에는 최소비용이 무제한인 경우를 구하면 되겠네요.

 

후기

좌표계를 그래프 형태로 바꾸는건 아직 익숙치 않아 그래프를 만드는데 애를 먹었던 문제입니다. 하지만 그래프만 제대로 만든다면 나머지는 전형적인 최대 유량 문제라 좋은 연습이 되었습니다. 네트워크 플로우 문제를 연습하는 사람들에게 추천하고 싶은 문제입니다.