BOJ 7152 Flooding Fields

문제 링크:

문제 내용

$n \times n$ 크기의 사각 격자 모양의 땅에 소가 $k$ 마리 서 있습니다. 한 칸에는 최대 한 마리의 소만 있을 수 있습니다.

다음 $h$ 시간 동안 이 땅에 물이 차서 수위가 바뀝니다. 어떤 시점에 어떤 소가 서 있는 칸의 땅 높이가 물의 높이 이하이면, 그 소는 익사하게 됩니다.

각각의 소는 한 시간마다 상하좌우로 이웃한 칸 중 하나로 이동하거나 그 자리에 있을 수 있습니다. 이때 $h$ 시간 이후에 살아남을 수 있는 소의 최대 마리 수를 구하세요.

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 입력은 0 0 0으로 종료됩니다.

첫 줄에 $n$ , $k$ , $h$ 의 값이 주어집니다. ( $1 \le n \le 100$ , $0 \le k \le 100$ , $1 \le h \le 24$ )

다음 $n$ 줄에는 각각 $n$ 개의 정수가 주어지는데, 이는 각 칸의 땅의 높이를 나타냅니다. 이 높이는 $0$ 이상 $100$ 이하입니다.

다음 $k$ 줄에는 각각의 소가 $0$ 시간째에 서 있는 위치의 행 번호 $r$ 과 열 번호 $c$ 가 주어집니다. 행 번호와 열 번호는 0에서부터 셉니다. ( $0 \le r, c < n$ )

다음 $h$ 줄에는 $1, \cdots, h$ 시간째의 물의 높이를 나타내는 정수가 한 줄에 하나씩 주어집니다. 물의 높이도 $0$ 이상 $100$ 이하입니다. 각각의 소는 물이 처음으로 차오르기 전에 한 번 이동할 기회를 갖습니다.

각 테스트 케이스에 대해, 살아남을 수 있는 소의 최대 마리 수를 한 줄에 출력합니다.

스포일러

이 문제는 플로우로 모델링할 수 있습니다. 1의 flow를 소 한 마리에 대응시키면 다음과 같은 모델링이 가능합니다.

각각의 좌표 $0 \le r, c < n$ 과 각 시간대 $0 \le t \le h$ 에 대해 노드 $a(r, c, t)$ 와 $b(r, c, t)$ 를 만들고, 별도의 source $s$ 와 sink $e$ 도 만듭니다.
각 시간대의 각 칸에 소가 한 마리만 있을 수 있음을 표현하기 위해, $a(r, c, t) \rightarrow b(r, c, t)$ 를 capacity 1의 간선으로 연결합니다.
각 시간대 사이에 각 소가 주변으로 한 칸 이동할 수 있음을 표현하기 위해, $\lvert r-r' \rvert + \lvert c-c' \rvert \le 1$ 인 경우 $b(r, c, t) \rightarrow a(r', c', t+1)$ 를 capacity 1의 간선으로 연결합니다.
각 소의 시작 위치 $(r, c)$ 에 대해 $s \rightarrow b(r, c, 0)$ 를 capacity 1의 간선으로 연결합니다.
가능한 모든 끝 위치 $(r, c)$ 에 대해 $a(r, c, h) \rightarrow e$ 를 capacity 1의 간선으로 연결합니다.
각 시간대에 소가 있을 수 없는 위치에 해당하는 노드들을 모두 제거합니다.

이를 Dinic으로 풀면 되는데, 시간이 굉장히 빡빡하므로 다음과 같은 최적화를 해야 통과할 수 있습니다.

소가 있을 수 있는 위치를 정확히 계산합니다. 이는 이전 시간에 가능한 소의 위치에서 1의 거리에 있는 위치들을 모두 체크한 다음 물에 잠긴 위치들을 모두 제거하는 것으로 구할 수 있습니다.
Dinic 구현체에 상수 최적화를 합니다. 노드 개수가 많을 때 residual graph의 구현에서 해시맵을 제거하는 방법이 존재합니다.

Last updated on 2025년 10월 30일 09:24:22