[BOJ][1346] 구슬 탈출 2

문제 : www.acmicpc.net/problem/13460

---

 

너비 우선 탐색(BFS)를 이용한다.

방문 여부는 빨간 공 (x, y) 파란 공 (x, y) 이용해서 4차원 배열을 만들어서 체크한다.(check 배열)

큐 안에는 (빨간 공(x, y), 파란 공(x, y), 기울인 횟수)를 저장한다.

벽 또는 탈출구가 나올 때까지 한 방향으로 공을 계속 움직인다.

파란 공이 빠져나오는 경우는 불가능한 경우이고 빨간 공만 나온 경우는 기울인 횟수를 출력하고 종료한다.

파란 공과 빨간 공이 겹치는 경우, 기울이기 전 위치를 비교해서 겹치지 않게 해준다.

만약, 아래 방향으로 움직이는 경우 기울이기 전 빨간 공이 파란 공보다 아래에 있었다면 파란 공의 위치를 1위로 옮긴다.

공들의 위치를 겹치지 않게 조정한 다음 check 배열에서 옮긴 빨간 공, 파란 공 위치를 아직 탐색하지 않았다면 큐에 넣는다.

이를 큐가 빌 때까지 반복하고, 큐가 빌 때까지 정답을 찾지 못했다면 -1을 출력한다.

 

---

소스코드

C++ :  github.com/fpdjsns/Algorithm/blob/master/BOJ/13460.%20%EA%B5%AC%EC%8A%AC%20%ED%83%88%EC%B6%9C%202.cpp

JAVA : gist.github.com/fpdjsns/c984d490b4c5e00e57683b66c922a062

---

 

TC : https://www.acmicpc.net/board/view/17710

몇 번 틀렸었는데,

1. 파란 공이 빠지는 경우

2. 10번 이하 조건

예외 처리를 안 해줘서 틀렸었다.

 

N, M이 최대 10이고 최대 10번 이동했을 때를 구하는 것으로 조건이 무척 작다.

그래서 check배열 없어도 무난하게 통과할 것 같다.