구슬탈출2

https://www.acmicpc.net/problem/13460

삼성 기출문제이다. 해설을 보고 이해하였다.

풀이

1. 완전탐색이고 최소 횟수를 구하는 것이므로, BFS를 사용한다.
2. 삼성 기출 문제 ‘2048’ 에서 블록 이동이 문제 해결의 관건이듯이, 이 문제 역시 공을 이동하는 것이 문제 해결의 관건이다.

구슬 이동 방법 : 상대 공을 무시하고 각자 공을 이동시킴

• B가 구멍에 빠지는 경우 : 큐에 넣지 않고 넘긴다
• B와 R이 겹치는 경우 : B와 R의 초기 상태를 확인해서 이동한다.
  • 예를 들어, 동쪽으로 이동하는 경우, 초기에 B가 R의 왼쪽에 있었다고 하자.
  • 그렇다면, B를 R의 왼쪽으로 한 칸 이동시켜야한다.