BOJ 13460. 구슬 탈출 2

13460번: 구슬 탈출 2 (acmicpc.net)

13460번: 구슬 탈출 2

2차원 배열 백트래킹 문제.

 

여기서 포인트는, 구슬이 한번에 두개가 동시에 움직인다는 것이다.

즉, 구슬을 기준으로 BFS로 이동시키면, 먼저 이동하는 구슬이 있으므로 구현할 수 없다.

따라서 판의 기울임을 기준으로 움직여주어야 한다.

 

이를 구현하려면 일단 판을 왼쪽으로 기울이는 swiping 함수가 필요하고

한쪽으로 기울이는 함수를 네 방향으로 적용하기 위해 네 방향으로 회전시키는 rotating 함수가 필요하다.

그리고 이를 backtracking으로 각 방향으로 회전시키며 swiping 함수를 실행해보면 된다.

 

여기서 주의할 점은 swiping함수를 구현할 때, 구슬이 들어갈 위치인 ind가 중요한데

중간에 벽으로 막힌 부분이 있으므로, #을 만나면 # 그 다음으로 ind를 조정해주어야 한다는 점이며

R, B가 모두 구멍에 들어갈 경우, R만 들어갈 경우를 따로 나눠주어야 한다.