문제 링크
- http://icpc.me/3055
문제 출처
- COCI 2006/2007 Contest #1 4번
사용 알고리즘
- BFS
시간복잡도
- o(n2m2)
풀이
KOI2017 2번 문명에서 사용한 아이디어(링크)를 이용했습니다.
문명 문제에서는 문명을 전파하는 bfs_propagation과 결합하는 bfs_union, 두 가지의 bfs 함수를 활용했습니다.
이 문제를 풀 때는 물을 퍼뜨리는 bfs_water와 고슴도치를 이동시키는 bfs_player라는 두 가지의 bfs를 사용했습니다.
bfs_water에서는 인접한 칸이 빈 칸이라면 물을 흘려 보냅니다.
bfs_player에서는 인접한 칸이 비어있고, 그 칸과 인접한 곳에 물이 없다면 go[x][y]를 갱신시켜 해당 좌표까지 가는 최소 시간을 계산해줍니다.
자세한 구현을 코드를 참고해주시기 바랍니다.