[BOJ] 백준 13460번: 째로탈출 2

째로탈출 2

문제

N*M 보드에 파란 구슬 빨간 구슬 구멍이 한 개씩 있고, 상하좌우 4방향으로 기울일 수 있을 때, 최소 몇 번 만에 빨간 구슬이 구멍에 나올 수 있는지 출력하는 문제이다. 단, 파란 구슬이 구멍으로 같이 나오면 실패이다.

문제 풀이

최대 10번 까지 보드를 조작할 수 있으므로, BFS 탐색을 이용하면 각 상태 공간에서 상하좌우 4방향으로 전이 가능 하고, 한 상태 공간에서 해당 방향으로 최대 \(max(N,M)\) 만큼 이동할 수 있으므로 \(O(4^{10} max(N,M))\) 임을 알 수 있다. 따라서 각 상태 공간 내에서 한 방향으로 이동 할 때

1. 빨간 구슬과 파란 구슬이 일직선 상에 없음

1.1) 빨간 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 성공

1.2) 파란 구슬이 가는 길에 구멍이 있는 경우 --> 탈출 실패

1.3) 구멍이 없는 경우 --> 구슬들을 최대한 이동한 후 큐에 push

2. 빨간 구슬이 가는 길에 파란 구슬이 있는 경우

2.1) 파란 구슬 앞에 구멍이 있는 경우 --> 탈출 성공

2.2) 파란 구슬 뒤에 구멍이 있는 경우 --> 탈출 실패

2.3) 구멍이 없는 경우 --> 파란 구슬은 최대한 이동, 빨간 구슬은 한 칸 덜 이동한 후에 큐에 push

3. 파란 구슬이 가는 길에 빨간 구슬이 있는 경우

3.1) 구멍이 있는 경우 --> 탈출 실패

3.2) 구멍이 없는 경우 --> 빨간 구슬은 최대한 이동, 파란 구슬은 한 칸 덜 이동한 후에 큐에 push

위의 과정을 bfs 각 상태 공간마다 시행하고 깊이가 10이 되면 종료하게 구현하면 된다.

 

소스 코드