[백준]JAVA - 13460번: 구슬 탈출 2

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

13460번: 구슬 탈출 2

풀이

생각했던 것보다 오래 걸렸던 문제였다.

 

위 문제에는 빨간 구슬과 파란 구슬 두 가지가 존재한다.

핵심은 빨간 구슬이 10번 이하로 움직여서 구멍에 들어가야한다. 또한, 빨간 구슬과 파란 구슬이 동시에 들어가면 안된다.

 

한 번의 움직임에 한 방향으로 벽이 나타날때까지 계속 움직일 수 있다. 빨간 구슬을 예로 살펴보겠다.

// 빨간 구슬
int nrx = now.rx;
int nry = now.ry;
				
while (true) {
    nrx += dx[i];
    nry += dy[i];
	
    // 구멍에 도달했을 경우
    if (map[nrx][nry] == 'O') {
        break;
    }
    
    // 벽을 만났을 경우
    if (map[nrx][nry] == '#') {
        nrx -= dx[i];
        nry -= dy[i];
        break;
    }
}

파란 구슬도 동일한 방법으로 이동시켜주면 된다. 빨간 구슬과 파란 구슬을 이동시켜준 직후에 주의할 게 있다. 바로, 빨간 구슬과 파란 구슬가 똑같은 위치에 있으며 빨간 구슬이 구멍에 도달하지 못 했을 경우이다. 이 경우에는 각 구슬이 이동한 거리를 계산해서 가까운 거리를 이동한 구슬을 그대로 두고, 멀리서 이동한 구슬을 한 칸 뒤로 되돌리면 된다.

 

마지막으로 방문 처리를 해줘야하는데 필자는 여기서 시간을 많이 소비했다. 2차원 배열을 두 개 생성해서 빨간 구슬과 파란 구슬을 따로 방문처리를 해줬다. visited 배열을 4차원으로 생성해서 방문처리를 해주면 쉽게 해결할 수 있다.

if (!visited[nrx][nry][nbx][nby]) {
    visited[nrx][nry][nbx][nby] = true;
    q.add(new Ball(nrx, nry, nbx,  nby, now.cnt+1));
}

 

<최종코드>

import java.io.*;
import java.util.*;
 
public class Main {
    static int N, M;
    static char[][] map;
    static int ans = -1;
	
    public static class Ball {
        int rx;
        int ry;
        int bx;
        int by;
        int cnt;
		
        public Ball (int rx, int ry, int bx, int by, int cnt) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.cnt = cnt;
        }
    }
	
    public static void main (String[] args) throws IOException {
        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];
        int rBx = 0;
        int rBy = 0;
        int bBx = 0;
        int bBy = 0;
		
        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') {
                    rBx = i;
                    rBy = j;
                }
				
                if (map[i][j] == 'B') {
                    bBx = i;
                    bBy = j;
                }
            }
        }
		
        bfs(new Ball(rBx, rBy, bBx, bBy, 0));
        System.out.println(ans);
    }
	
    public static void bfs (Ball b) {
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
		
        boolean[][][][] visited = new boolean[N][M][N][M];
        Queue<Ball> q = new LinkedList<>();
		
        visited[b.rx][b.ry][b.bx][b.by] = true; 
        q.add(b);
		
        while (!q.isEmpty()) {
            Ball now = q.poll();
			
            // 10번 횟수 제한
            if (now.cnt > 10) {
                ans = -1;
                return;
            }
			
            // 파란 구슬이 들어간 경우
            if (map[now.bx][now.by] == 'O') {
                continue;
            }
			
            // 빨간 구슬이 들어간 경우
            if (map[now.rx][now.ry] == 'O') {
                ans = now.cnt;
                return;
            }
			
            for (int i=0; i<4; i++) {
				
                // 빨간 구슬
                int nrx = now.rx;
                int nry = now.ry;
				
                while (true) {
                    nrx += dx[i];
                    nry += dy[i];
					
                    if (map[nrx][nry] == 'O') {
                        break;
                    }
					
                    if (map[nrx][nry] == '#') {
                        nrx -= dx[i];
                        nry -= dy[i];
                        break;
                    }
                }
				
                // 파란 구슬
                int nbx = now.bx;
                int nby = now.by;
				
                while (true) {
                    nbx += dx[i];
                    nby += dy[i];
					
                    if (map[nbx][nby] == 'O') {
                        break;
                    }
					
                    if (map[nbx][nby] == '#') {
                        nbx -= dx[i];
                        nby -= dy[i];
                        break;
                    }
                }
				
                // 빨간 구슬이 구멍에 도착하지않고 파란 구슬과 빨간 구슬이 똑같은 위치에 있는 경우
                if (nrx == nbx && nry == nby && map[nrx][nry] != 'O') {
                    int rDis = Math.abs(now.rx - nrx) + Math.abs(now.ry - nry);
                    int bDis = Math.abs(now.bx - nbx) + Math.abs(now.by - nby);
					
                    if (rDis > bDis) {
                        nrx -= dx[i];
                        nry -= dy[i];
                    } else {
                        nbx -= dx[i];
                        nby -= dy[i];
                    }
                }
				
                if (!visited[nrx][nry][nbx][nby]) {
                    visited[nrx][nry][nbx][nby] = true;
                    q.add(new Ball(nrx, nry, nbx,  nby, now.cnt+1));
                }
            }
        }
    }
}

내가 생각한 시간복잡도: O(4NM)