The King of the North( BOJ 9209 )

문제

9209. The king of the north : https://www.acmicpc.net/problem/9209

9209번: The King of the North

 

문제 파악하기

• 격자칸마다 해당 지력을 지키기 위해 필요한 병사의 수가 주어지고, 성을 지키기 위해 필요한 최소 병사 수를 구해야 합니다.
• 입력되는 격자칸의 크기가 최대 300으로 크지 않습니다. 이런 경우 최대 유량을 의심할 수 있습니다.
• 성을 지킨다는 건 성에서 와부로 나가는 경로 상의 값 중 최솟값을 찾아 막으면 됩니다.
• 경로 값 중 촤솟값만을 찾는 건 결국 최소컷을 구하는 문제와 의미가 같아집니다.

 

문제 해결하기

• 우선 격자판의 좌표들을 정점으로 표현해야 합니다.
  물론 시작점은 성의 좌표, 도착점은 격자 밖의 모든 좌표값입니다.
• 정점과 정점 사이의 용량은 무제한으로 두어야 합니다. 격자판에서 좌표를 이동하는 데에는 제한이 없기 때문입니다.
• 다만, 이 문제에서는 정점을 분할해야 합니다.
  최소컷의 개념 자체가 목적지까지 이동할 수 없도록 간선을 자르는데 필요한 최소값을 의미하기 때문입니다.
• 따라서 간선을 두개로 분할하여 들어오는 정점과 나가는 정점으로 나누면 됩니다.
  그리고 분할한 두 정점을 하나의 간선으로 연결하고, 이 때에는 해당 지역을 지키는데 필요한 병사의 수로 가중치를 둡니다.
• 이렇게 모델링을 하면 성에서 외부까지 나가는 경로를 탐색하며 격자판을 지날 때에만 필요한 병사 수를 체크하게 됩니다.
• 나머지는 최대 유량 알고리즘을 이용하면 풀 수 있습니다.

 

후기

최대 유량 문제는 모델링이 참 중요해보입니다. 이 문제는 Cops and Robbers(www.acmicpc.net/problem/16407)와 상당히 유사해보니 같이 풀어보면 좋은 문제라고 생각이 듭니다.