[백준 13460]구슬 탈출 2/삼성 sw역량 테스트 기출(java)

문제 보러 가기

13460번: 구슬 탈출 2

이 문제는 예전에 풀려다가 실패하고 까먹었었던 문제인데 이번에 다시 풀어보았다. bfs 탐색을 하며 빨간 구슬 R이 구멍이 O에 들어갈 수 있는지 확인하는 문제이다.

 

 

 

 

 

 

 

* 놓칠 수 있는 조건들

1. 10번 이상 움직여야 하는 경우 구슬을 탈출시킬 수 없다고 판단. -1을 return 해야 함

2. 구슬의 위치를 바꿨다면 이전 구슬의 위치는 삭제 후 탐색해야 함

3. 구슬 두 개의 위치로 방문 체크를 해야 함. R은 같은 위치 B만 바뀔 경우 탐색 대상이기 때문

4. 두 구슬은 같은 위치에 있을 수 없음

    =>  #.R.B..# 에서 →(오른쪽) 방향으로 움직인다면 #...RB# 이렇게 됨

5. B구슬이 O에 빠진다고 바로 -1을 return 하면 안 됨. 4방향을 다 체크해야 함

6. R이 먼저 빠진다고 답을 return 하면 안 됨. 해당 이동방향에서 B도 구멍에 빠질 경우 정답이 아니기 때문

    => B 먼저 탐색하는 이유

 

 

문제풀이

- 초기 R, B위치를 저장하고 map에 기록되어있는 R, B는 빈칸인.으로 바꾼다.

- 4방향에서 한 칸만 이동 x => #까지 가거나 R과 B가 붙어있을 때까지 쭉 탐색

-> visited [R.x][R.y][B.x][B.y]로 탐색 여부 확인하면서 탐색

-

B가 구멍에 빠진다면 해당 방향은 탐색할 필요가 없으므로 oFlag를 통해 표시해주고 break

 

- B의 이동방향에 R이 있다면 R의 한칸뒤에 B가 위치하게 됨. flag를 통해 표시해주고 R탐색

-> 이경우 만약 R이 구멍에 빠지게 된다면 B 역시 같이 빠지므로 답이 아님

 

 

 

 

 

 

public class Ex_13460 {

	static int n, m;
	static char[][] map;
	static boolean[][][][] visited;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		// 삼성 sw역량 테스트-구슬탈출 2

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		visited = new boolean[n][m][n][m];
		Pair red = null;
		Pair blue = null;
		for (int i = 0; i < n; i++) {
			String s = br.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'R') {
					red = new Pair(i, j, 0);
					map[i][j] = '.';
				} else if (map[i][j] == 'B') {
					blue = new Pair(i, j, 0);
					map[i][j] = '.';
				}
			}
		}
		System.out.println(bfs(red, blue));
	}

	static int bfs(Pair red, Pair blue) {
		Queue<Pair> redQ = new LinkedList<>();
		Queue<Pair> blueQ = new LinkedList<>();
		redQ.add(red);
		blueQ.add(blue);

		while (!redQ.isEmpty() && !blueQ.isEmpty()) {
			Pair curR = redQ.poll();
			Pair curB = blueQ.poll();
			if (curR.time+1 > 10) //10번까지만 이동가능
				return -1;
			for (int i = 0; i < 4; i++) {
				int rx = curR.x;
				int ry = curR.y;
				int bx = curB.x;
				int by = curB.y;
				boolean flag = false;// 이동방향에 빨간색 구슬이 있을경우
				boolean oFlag = false;// 파란구슬이 구멍에 빠질경우
				visited[rx][ry][bx][by] = true;
				while (true) {
					bx += dx[i];
					by += dy[i];
					if (bx == rx && by == ry) { //이동방향에 R이 있다면
						flag = true;
						break;
					}
					if (map[bx][by] == '#') { //B인덱스를 갱신 
						bx -= dx[i];
						by -= dy[i];
						break;
					}
					if (map[bx][by] == 'O') { //B가 구멍에 빠졌을 경우
						oFlag = true;
						break;
					}
				}
                //B가 구멍에 빠진다면 탐색할필요가 없음
				while (!oFlag) {
					rx += dx[i];
					ry += dy[i];
					if (rx == bx && ry == by) {//이동방향에 B가 있다면
                    	//B는 위의 while문에서 이미 #을 만나서 정지한상태
                        //B의 뒤의 인덱스에 R이 위치, 큐에 저장
						if (!visited[rx - dx[i]][ry - dy[i]][bx][by]) {
							redQ.add(new Pair(rx - dx[i], ry - dy[i], curR.time + 1));
							blueQ.add(new Pair(bx, by, curB.time + 1));
						}
						break;
					}
					if (map[rx][ry] == '#') {
						if (!visited[rx - dx[i]][ry - dy[i]][bx][by]) {
							redQ.add(new Pair(rx - dx[i], ry - dy[i], curR.time + 1));
                            //위의 while문에서 B가 R을 만나 탐색을 종료하였으므로
                            //R의 뒤의 인덱스에 B가 위치, 큐에 저장
							if (flag)
								blueQ.add(new Pair(rx - dx[i] - dx[i], ry - dy[i] - dy[i], curR.time + 1));
							//R을 만나 종료된 상태가 아니라면 원래의 B의 인덱스로 저장
                            else
								blueQ.add(new Pair(bx, by, curB.time + 1));
						}
						break;
					}
                    
					if (map[rx][ry] == 'O') {
                    //구멍을 만났지만 B가 붙어있는 경우 flag==true
						if (oFlag || flag) {
							break;
						}
						return curR.time + 1;
					}
				}
			}
		}
		return -1;
	}

	static class Pair {
		int x;
		int y;
		int time;

		Pair(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}

}

* 지금 다시 보니 정리할만한 코드가 있을 거 같다...