BOJ 13460번 구슬 탈출2 문제 자바(java) 풀이
문제 정리
문제에 요구사항이 꽤 있으므로 잘 읽으시기 바랍니다!!
- 구슬 탈출: 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임
- NxM 크기의 보드, 1x1칸으로 나누어져 있음. 빨간 구슬을 구멍을 통해 빼내야 하며, 파란 구슬이 구멍에 들어가면 안됨
- 왼쪽, 오른쪽, 위쪽, 아래쪽으로 보드를 기울일 수 있다.
- 빨간 구슬이 구멍에 빠지면 성공, 파란색이 빠지면 실패. 동시에 빠져도 실패
- 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
- 더 이상 구슬이 움직이지 않을때까지 기울여본다.
- 보드의 상태가 주어질때 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하여라
- .: 빈칸, #: 공이 이동할 수 없는 장애물, o: 구멍의 위치, R: 빨간 구슬의 위치, B:파란 구슬의 위치
- 보드의 가장자리는 모두 #이며 빨간, 파란 공은 1개씩 주워지고 구멍도 한 개만 주어진다.
- 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
- 기울여서 한 칸씩 움직이는 것이 아니라 굴러간다...
문제 풀이
이해한 내용에 맞춰서 예제를 머릿속이나 손으로 한 번 해봤어야 했는데
그러지 못해서 문제 이해를 잘 못해서 시간이 좀 걸렸습니다.
- 기울여서 한 칸씩 움직이는것이 아니라 한쪽으로 움직이면 벽을 만나거나 다른 공을 만날때까지 굴러갑니다.
- bfs 방법을 통해 탐색합니다. 방문 여부는 4차원 배열을 통하여 저장합니다.
- queue에 빨간공의 위치, 파란공의 위치, 이동 횟수를 담은 Pair를 넣습니다.
- 우선 누가 먼저 움직이는지 결정해야 합니다.
빨강/파랑이 붙어 있다면 왼쪽으로 움직일때 빨강먼저 움직여야 합니다. 파랑 먼저 움직인다면 빨강과 파랑이 겹치기 때문입니다.
- 누가 먼저 움직이는지 결정되었다면 빨강, 파랑이 한 칸씩 움직여 갑니다.
그러다가 구멍에 도달하거나 벽을 만나거나 겹치는 경우, 가운데 있는 벽을 만난 경우 움직임을 멈추게 됩니다. 그 전까지는 계속 움직입니다.
- 두 구슬 모두 더 이상 움직일 수 없는 경우 while문을 탈출하여 움직이지 않습니다.
- 파랑 구슬이 구멍에 빠진 경우는 실패이므로 다른 방향으로 움직이기 위해 continue 합니다.
- 빨강 구슬이 빠진 경우 min 값을 update 해줍니다.
- 방문하지 않았다면 queue에 넣고 방문처리 해줍니다.
백준 13460번 구슬 탈출2
- 메모리: 13284 kb
- 실행시간: 80 ms