풀이
간만에 그래프탐색 문제이다.
두 개의 구슬이 위치한 보드를 기울여서 빨간구슬만 10번안에 탈출시키면 성공하는 게임이다.
처음엔 각 구슬에 대하여 BFS 를 실행하면 되는 줄 알았는데 방문처리가 문제여서 다른분들의 풀이를 참고하면서 풀었다.
타 BFS 문제들과의 차이점이 있었는데,
-
이동한 방향이 벽에 닿을 때 까지 혹은 도착점에 도착할 때 까지 같은 방향으로 쭉 이동해야 한다는 조건.
-
두 구슬이 함께 움직인다는 조건.
위 두가지 조건을 모두 충족시키면서 문제를 풀어야했다.
move() 함수를 새로 정의하면서 각 방향마다 벽에 닿거나 도착점에 도착할 경우까지 이동 후 좌표를 리턴해주는 식으로 구현하였고 이 때 두 개의 구슬이 함께 움직이기 때문에 겹칠 가능성을 고려하여 얼마나 이동했는지를 판단할 c 값을 추가로 리턴해주었다.
이동 후 파란 구슬은 도착점에 도착하지 않고 빨간 구슬만 도착점에 도착했다면 정답이기 때문에 현재까지 몇 번 기울였는지 출력하고 종료하면된다.
만약 두 개의 구슬이 겹쳤을 경우 더 많이 이동한 구슬이 뒤쪽에 위치해야하기 때문에 해당 구슬의 좌표를 한 칸 밀어서 배치해준다.
만약 정답이 나오지 않았으며 두 구슬의 위치가 방문하지 않았던 경우라면 해당 값들을 큐에 다시 삽입해준 뒤 위 과정을 반복한다.
소스코드
References