백준 B3197-백조의 호수 with 파이썬

문제 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXX... www.acmicpc.net 풀이 진짜 힘들었다. 처음으로 풀어본 플래티넘 단계의 문제였다.

역시 플래티넘의 벽은 진짜 높은 것 같다. 단순한 BFS라고 생각하고 들어갔다가 호되게 혼난 문제다.

범위가 너무 커서 시간초과가 날 걸 알면서도 처음엔 아이디어가 생각나지 않아서 고생했다. 그러나 최적화를 계속 고민하다보니 빠르...