[백준 / BOJ] 13460번 : 구슬 탈출2 (JAVA)

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

BFS : 방문 체크

나는 시뮬레이션 문제를 보통 난잡하고... 얼기설기 푸는 편인데 이 문제도 어김없이 굉장히 더럽게 풀고 말았다.

 

최단 시간을 정하는 문제이기 때문에 BFS를 선택했다. 경우의 수가 많아질 것 같으면 DFS를 쓰지 않는다. 스택오버플로우가 날 것 같기 때문이다.

 

방문 체크는 v[빨간 공 행][빨강 공 열][파란 공 행][파란 공 열] 로 진행했다. map의 상태가 정확히 일치하도록 한 것이다. 빨간 공이 다시 온 곳이 이미 방문했던 곳이라도, 파란 공은 전혀 모르는 곳에 갔다면 다음 경우의 수가 달라지기 때문이다. 또 최대 10 * 10 * 10 * 10 = 10,000 이라 메모리 초과에 걸리지 않았다.

if(!v[red[0]][red[1]][blue[0]][blue[1]]) {
    v[red[0]][red[1]][blue[0]][blue[1]] = true;
    que.offer(new int[] {red[0], red[1], blue[0], blue[1], cur[4] + 1});

}

 

굴릴 순서 정하기

 

구슬을 움직이기 전에 먼저 떠올린 것은 '어떤 구슬을 먼저 움직이게 할 것인가?' 였다. 현실에서는 두 구슬이 같이 움직이겠지만 코드를 짤 때는 어쨌든 선후가 정해질 수 밖에 없기 때문이다. 구슬 두 개가 따로 떨어져 있다면 상관 없지만 만일 나란히 놓여있다면 움직이기 전 구슬에 가로막힐 수도 있다.

 

따라서 구슬을 움직이기 전에 같은 열, 혹은 같은 행에 있는지 체크하고 만일 같이 있다면 순서를 따져서 움직일 수 있는 함수를 만들었다. first가 먼저 움직이고, 항상 second가 나중에 움직인다. red와 blue의 위치는 Array로 호출했기 때문에, 리턴값은 따로 두지 않았다. Array는 바뀐 내용으로 돌아오니까.

if(red[1] == blue[1]) {
    if(d == 0 && red[0] < blue[0]) {
        move_ball(red, blue, d, map);
    } else if(d == 0){
        move_ball(blue, red, d, map);
    } else if(d == 2 && red[0] < blue[0]) {
        move_ball(blue, red, d, map);
    } else if(d == 2) {
        move_ball(red, blue, d, map);
    } else {
        move_ball(red, blue, d, map);
    }
} else if(red[0] == blue[0]) {
    if(d == 1 && red[1] < blue[1]) {
        move_ball(red, blue, d, map);
    } else if (d == 1) {
        move_ball(blue, red, d, map);
    } else if (d == 3 && red[1] < blue[1]) {
        move_ball(blue, red, d, map);
    } else if (d == 3) {
        move_ball(red, blue, d, map);
    } else {
        move_ball(red, blue, d, map);
    }
} else {
    move_ball(red, blue, d, map);
}

단, red와 blue라는 배열은 계속 사용해야 하기 때문에 방문 체크를 한 후에는 꼭 cur로 초기화 해주었다.

 

구슬 굴리기

구슬은 두 개 모두 한 칸씩 굴려주었다. 다시 생각해보니 선을 정했으니만큼 그냥 끝까지 돌리고 두 번째 구슬을 끝까지 돌려도 됐을 것 같다.

 

아무튼 더이상 굴러갈 수 있을지를 표시하는 f와 s를 두고, first의 경우 다음과 같이 움직이게 했다.

 

1) 다음 칸이 . 이면 옮겨 간다.
2) 다음 칸이 'O'이면 굴러간 다음 '더이상 구를 수 없음' 표시를 한다.
3) 다음 칸이 '#'이면 굴러가지 않고 '더이상 구를 수 없음' 표시를 한다.

 

주의할 점은 'O'에 도착하더라도 바로 끝내지 않는 것이다. 두 번째 공이 세 턴, 네 턴 후에 O에 빠질 수도 있으니까.

 

second의 경우에는 다음과 같이 움직였다.

 

1 - 1) 다음 칸이 . 이고, 그곳에 다른 공이 없다면 움직인다.
1 - 2) 다음 칸이 . 이고, 그곳에 다른 공이 있다면 현재 위치를 유지하면서 return한다. (앞의 공도 더이상 움직일 수 없어서 남아있는 것이기 때문이다)
2) 다음 칸이 'O' 라면 다음 칸으로 굴러가고, return한다
3) 다음 칸이 '#'라면 '더이상 구를 수 없음' 표시를 한다.

 

 

7% 틀렸습니다 : 다른 경우 찾기

가장 처음에는 7%에서 틀렸습니다를 받았는데, 다음 코드 때문이었다.

if(map[red[0]][red[1]] == 'O') {
    if(map[blue[0]][blue[1]] != 'O') {
        System.out.println(cur[4]);
        System.exit(0);
    } else break;
}

빨간 공이 O에 도달했을 때 만일 파란 공 역시 O에 도달했다면 바로 탐색을 중지하고 while문 밖으로 나가게 했다. 하지만 문제에서는 빨간 공이 혼자 O에 도달할 수 있는 최소 시간을 요구했기 때문에, 만일 어떤 경우의 수에서 3번 째에 빨간 공, 파란 공이 모두 O에 빠지고, 다른 경우의 수에서 5번 째에 빨간 공만 O에 빠진다면 답은 5가 되는 것이다. 즉, 한 번 실패했다고 while문을 빠져나가면 안된다.

 

break을 continue로 변경해주고 7%를 넘겼다. O에 빠지는 경우이긴 하니 그 다음 수를 볼 필요는 없기 때문이다.

 

14% 틀렸습니다 : 파란 공만 O에 빠지는 경우

그 다음 틀린 이유는 '파란 공만 O에 빠지는 경우'를 생각하지 않았기 때문이다. 기존 코드에서는 파란 공만 O에 빠진 경우 다음 수로 계속 진행해 버렸다. 이미 공이 빠진 순간 그 경우의 수는 끝이기 때문에 다음 코드를 추가했다.

if(map[blue[0]][blue[1]] == 'O') continue;

 

여기까지 수정하고 정답을 제출할 수 있었다.

 

 

전체 코드

// 시간 : 96ms
// 메모리 : 13040KB
public class Main {

	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		char[][] map = new char[N][M];
		
		int[] red = new int[2];
		int[] blue = new int[2];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == 'R') {
					red[0] = i;
					red[1] = j;
					map[i][j] = '.';
				} else if(map[i][j] == 'B') {
					blue[0] = i;
					blue[1] = j;
					map[i][j] = '.';
				}
			}
		}
		
		boolean[][][][] v = new boolean[N][M][N][M];
		
		Queue<int[]> que = new LinkedList<>();
		que.offer(new int[] {red[0], red[1], blue[0], blue[1], 0});
		v[red[0]][red[1]][blue[0]][blue[1]] = true;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			red[0] = cur[0];
			red[1] = cur[1];
			blue[0] = cur[2];
			blue[1] = cur[3];
			
			if(cur[4] > 10) break;
			if(map[red[0]][red[1]] == 'O') {
				if(map[blue[0]][blue[1]] != 'O') {
					System.out.println(cur[4]);
					System.exit(0);
				} else continue;
			}
			
			if(map[blue[0]][blue[1]] == 'O') continue;
			
			for (int d = 0; d < 4; d++) {
				
				if(red[1] == blue[1]) {
					if(d == 0 && red[0] < blue[0]) {
						move_ball(red, blue, d, map);
					} else if(d == 0){
						move_ball(blue, red, d, map);
					} else if(d == 2 && red[0] < blue[0]) {
						move_ball(blue, red, d, map);
					} else if(d == 2) {
						move_ball(red, blue, d, map);
					} else {
						move_ball(red, blue, d, map);
					}
				} else if(red[0] == blue[0]) {
					if(d == 1 && red[1] < blue[1]) {
						move_ball(red, blue, d, map);
					} else if (d == 1) {
						move_ball(blue, red, d, map);
					} else if (d == 3 && red[1] < blue[1]) {
						move_ball(blue, red, d, map);
					} else if (d == 3) {
						move_ball(red, blue, d, map);
					} else {
						move_ball(red, blue, d, map);
					}
				} else {
					move_ball(red, blue, d, map);
				}
				
				if(!v[red[0]][red[1]][blue[0]][blue[1]]) {
					v[red[0]][red[1]][blue[0]][blue[1]] = true;
					que.offer(new int[] {red[0], red[1], blue[0], blue[1], cur[4] + 1});
					
				}
				red[0] = cur[0];
				red[1] = cur[1];
				blue[0] = cur[2];
				blue[1] = cur[3];
			}
			
		}
		
		System.out.println(-1);
	}
	
	
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,-1,0,1};
	private static void move_ball(int[] first, int[] second, int d, char[][] map) {
		
		int fr = first[0];
		int fc = first[1];
		int sr = second[0];
		int sc = second[1];
		
		boolean f = true;
		boolean s = true;
		
		while(true) {
			int nr1 = fr + dr[d];
			int nc1 = fc + dc[d];
			int nr2 = sr + dr[d];
			int nc2 = sc + dc[d];
						
			if(f) {
				if(map[nr1][nc1] == '.') {
					fr = nr1;
					fc = nc1;
				} else if(map[nr1][nc1] == 'O') {
					fr = nr1;
					fc = nc1;
					f = false;
				} else {
					f = false;
				}
			}
			
			if(s) {				
				if(map[nr2][nc2] == '.') {
					if(fr == nr2 && fc == nc2) {
						first[0] = fr;
						first[1] = fc;
						second[0] = sr;
						second[1] = sc;
						return;
					} else {
						sr = nr2;
						sc = nc2;
					}
				} else if(map[nr2][nc2] == 'O') {
					first[0] = fr;
					first[1] = fc;
					second[0] = nr2;
					second[1] = nc2;
					return;
				} else {
					s = false;
				}
			}
			
			if(!f && !s) {
				first[0] = fr;
				first[1] = fc;
				second[0] = sr;
				second[1] = sc;
				break;
			}
		}
		return;
	}

}