구슬 탈출 2

[python3] 백준 14360 풀이 ( 구슬 탈출 2, BFS, 방문체크 없음 )

이번 문제는 저번 주 스터디에서 풀지 못한 문제였는데, 생각할 시간이 상당히 많았기 때문에 겨우 풀었다. 우선 문제를 살펴보자 문제를 요약하면 상하좌우로 움직일 수 있는 판을 가지고 있을 때, 빨간공만을 출구로 뽑아내는 경우 얼마나 시간이 걸리는지 알아내는 문제이다. 이때 한 방향으로 움직이는 경우 두 공이 못 움직일 때까지 움직인다. 우선 우리는 최소로 움직여서 공을 뽑아낼 것이다. 즉, 최단 거리나 최단 경우의 수를 구할 때는 역시 BFS를 사용해야한다. 두번째로 우리는 2공(빨강,파랑)을 상하좌우로 움직일 것이다. 움직일 때는 한번에 움직이지 못하고 한 칸씩 이동하면서 움직여야한다. 왜냐하면 그래야 겹치는 경우를 피할 수 있다. 그런데 겹치는 경우를 위해 한 칸씩 움직인다고 한다면 방향에 따라 두 ..