[백준 13460번] 구슬 탈출 2 (java)

 

사용한 방법 : BFS

 

빨간 구슬의 위치를 넣는 큐와 파란 구슬의 위치를 넣는 큐 이렇게 두 개의 큐를 생성한다.

각각의 큐에는 기울이기를 통해 움직이고 난 후의 빨간구슬의 위치와 파란구슬의 위치 정보가 들어있다.

 

Queue<Pos> redque = new LinkedList<>();

Queue<Pos> blueque = new LinkedList<>();

 

Pos 클래스는 구슬의 위치(n, m)과 구슬이 해당 위치에 도달했을 때 총 움직인 횟수 move 가 들어간다.

	static class Pos {

		int n, m, move;

		Pos(int n, int m, int move) {
			this.n = n;
			this.m = m;
			this.move = move;
		}
	}

 

한 번 기울이면 구슬은 장애물(벽 혹은 다른 구슬)에 부딪힐 때까지 한칸씩 움직인다.

기울이기를 수행한 후 빨간구슬과 파란구슬이 완전히 멈추면, 두 구슬의 위치를 각각의 큐에 넣는다.

상,하,좌,우 4가지의 방향이 있으므로 4번의 기울이기를 한다.

 

그런데 파란구슬이 구멍에 빠지는 경우에는 움직인 구슬의 위치를 큐에 넣어주면 안된다.

특정 방향으로 기울이기를 수행했을 때 파란구슬이 구멍에 빠지게 된다면, 그 방향으로는 기울이기를 하면 안된다. 파란구슬이 구멍에 빠지는 순간 이미 게임이 실패하기 때문이다.

 

따라서 기울이기를 했을 때, 빨간구슬이 구멍에 빠지더라도 여기서 끝이 아니라 그 이후에 파란구슬이 구멍에 빠지는지를 확인해야한다. 만약 빨간구슬도 구멍에 빠지고, 파란구슬도 구멍에 빠지면 게임 실패이므로 역시 마찬가지로 해당 방향으로 기울이기를 해서는 안된다. 

 

 

한 번 기울기가 끝난 후, 그 사이에 구슬들이 구멍에 빠졌는지 여부는 redflag와 blueflag로 판단한다.

redflag = true이면 빨간구슬이 구멍에 빠졌음을 의미하고, 

blueflag = true이면 파란구슬이 구멍에 빠졌음을 의미한다.

 

• blueflag=true : 큐에 새로 갱신된 위치를 넣지 않고 다른 방향의 기울이기를 수행한다.

• redflag=true && blueflag=false : bfs를 종료하고 여태까지 기울이기를 한 횟수가 정답이다.

• redflag=false && blueflag=false : 빨간 구슬과 파란 구슬 각각의 새로운 위치를 큐에 넣는다.

		if (redflag && !blueflag)
			return redPos.move;

		if (!blueflag) {
			redque.add(redPos);
			blueque.add(bluePos);
		}

 

구슬의 이동후에는 구슬의 이동 전에 원래 구슬위치에 있던 문자 'R'과 'B'를 '.'로 변경한다.

(처음에 이렇게 하지 않아서 반복문이 반복될수록 'R'과 'B'가 난무하게 되는 문제가 생겼음)

if (board[redPos.n][redPos.m] == 'R')
	board[redPos.n][redPos.m] = '.';
if (board[bluePos.n][bluePos.m] == 'B')
	board[bluePos.n][bluePos.m] = '.';

 

 

큐에서 새로운 위치를 꺼낼 때는 빨간 구슬의 기울인 횟수를 체크해서 기울이기를 한 횟수가 10보다 크거나 같으면 반복문을 종료하고 -1을 반환한다.

 

 

전체코드 :