[백준 / BOJ] 13460 구슬 탈출 2

문제

출처 : www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

보드의 가로, 세로의 길이가 주어지고, 두 구슬 R,B의 위치가 주어진다.

 

보드를 기울여 구슬을 동서남북으로 움직일수있다. 단, 한번 움직이면, 벽, 다른 구슬, 구멍을 만날때까지 기울인 방향으로 움직여야한다.

 

R구슬만 탈출시키는 최소한의 이동 횟수를 구하면 된다.

 

풀이

시키는대로 하면되는 구현문제다.

 

BFS알고리즘을 이용해 풀었다.

 

- check배열을 4차원으로 선언해서 체크해줬다. (check[빨간구슬y][빨간구슬x][파란구슬y][파란구슬x] = 도달한 최소이동횟수) 

최소이동 횟수를 구해야하므로 최소이동횟수보다 많은 이동횟수로 인덱스에 도착하면 항상 틀린다.

 

1. 현재 위치에서 빨간구슬과 파란구슬을 동시에 동, 서, 남, 북으로 이동시킨다.

(이동은 BFS로 안하고 반복문을 이용해 다음 이동조건을 만족할때까지 반복시켰다.)

 

- 이동조건

1. 빨간구슬과 파란구슬을 둘다 움직일수없으면 break

2. 빨간구슬과 파란구슬 모두 구멍에 빠지지 않았는데, 같은 위치에 도착하면 break

3. 두 구슬이 모두 구멍에 빠졌다면 break

 

2. 빨간구슬만 빠지지 않았다면, 다시 queue에 넣고 탐색한다.

 

3. 만약 빨간구슬만 빠졌다면 이동횟수를 출력하고 종료한다.

 

기울인 방향으로 이동중 빨간구슬이 빠짐과 동시에 출력하면 안되고, 이동이 끝났을때 두 구슬 모두 빠지지않았다면 출력해줘야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/13460%20%EA%B5%AC%EC%8A%AC%20%ED%83%88%EC%B6%9C%202/main.cpp

devxb/JJUNalgo