백준 13460 구슬 탈출2 자바(java)

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

13460번: 구슬 탈출 2

 

풀이 방법

DFS + 백트래킹을 이용하여 풀었다.

DFS 시 방문 체크는 빨간 구슬 좌표와 파란 구슬 좌표를 인덱스로 하는 4차원 배열 visited 을 선언해주었다.

풀이 흐름은 아래와 같다.

 

1. 현재 기울이는 방향대로 구슬을 이동시키는데, 이때 다른 구슬은 신경쓰지 않고 벽까지 이동시킨다.

2. 이동 후의 두 구슬이 같은 칸에 위치한다면 위치 조정을 한다.

    두 구슬 각각의 이동 거리를 계산한 결과 더 먼 거리를 온 구슬이 뒤에 있던 구슬이다.

    따라서, 뒤에 있었던 구슬의 좌표를 한 칸 뒤로 이동시킨다.

3. 현재 빨간 구슬 좌표와 파란 구슬 좌표에 해당하는 visited 값이 false 라면 dfs 함수에 현재 좌표들을

    넘겨 재귀 호출하여 다시 1번부터 탐색한다.

4. 재귀 호출이 완료되면 백트래킹하여 원 상태로 복구한 후 다른 방향에 대해 다시 1번부터 탐색한다.

 

 

코드

import java.io.*;

public class Main {

    static int N;
    static int M;
    static char[][] board;
    static int answer = Integer.MAX_VALUE;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {-1, 0, 1, 0};
    static boolean[][][][] visited;
    static boolean success = false;

    public static void main(String[] args) throws Exception  {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        board = new char[N][M];
        visited = new boolean[N][M][N][M];
        int rx = 0, ry = 0; // 빨간 구슬 좌표
        int bx = 0, by = 0; // 파란 구슬 좌표

        for(int i=0; i<N; i++) {
            String row = br.readLine();
            for(int j=0; j<M; j++) {
                board[i][j] = row.charAt(j);
                if(board[i][j] == 'R') {
                    rx = i;
                    ry = j;
                } else if(board[i][j] == 'B') {
                    bx = i;
                    by = j;
                }
            }
        }

        dfs(0, rx, ry, bx, by);
        if(success) {
            System.out.println(answer);
        } else {
            System.out.println(-1);
        }

    }

    public static void dfs(int num, int rx, int ry, int bx, int by) {
        // 10번까지만
        if(num == 10) {
            return;
        }
        visited[rx][ry][bx][by] = true; // 방문 체크

        for(int i=0; i<4; i++) {
            // 구슬이 이동할 좌표 위치
            int _rx = rx;
            int _ry = ry;
            int _bx = bx;
            int _by = by;
            boolean redHole = false;
            boolean blueHole = false;
            // 빨간 구슬 이동
            while(board[_rx + dx[i]][_ry + dy[i]] != '#') {
                _rx += dx[i];
                _ry += dy[i];
                // 구멍이면
                if (board[_rx][_ry] == 'O') {
                    redHole = true;
                    break;
                }
            }
            // 파란 구슬 이동
            while(board[_bx + dx[i]][_by + dy[i]] != '#') {
                _bx += dx[i];
                _by += dy[i];
                // 구멍이면
                if (board[_bx][_by] == 'O') {
                    blueHole = true;
                    break;
                }
            }

            if(blueHole) { // 파란 구슬이 빠지면 실패
                continue;
            }

            if(redHole){ // 빨간 구슬만 빠지면 성공
                answer = Math.min(answer, num+1);
                success = true;
                break;
            }

            // 구슬의 위치 조정
            if(_bx == _rx && _by == _ry) {
                int redDist = Math.abs(rx - _rx) + Math.abs(ry - _ry);
                int blueDist = Math.abs(bx - _bx) + Math.abs(by - _by);
                // 파란 공이 앞에 있었던 경우 빨간 공을 뒤로
                if(redDist > blueDist) {
                    _rx -= dx[i];
                    _ry -= dy[i];
                } else { // 빨간 공이 앞에 있었던 경우 파란 공을 뒤로
                    _bx -= dx[i];
                    _by -= dy[i];
                }
            }

            // 두 구슬의 위치 상태가 처음 방문하는 상태인 경우만
            if(!visited[_rx][_ry][_bx][_by]) {
                board[rx][ry] = '.';
                board[bx][by] = '.';
                board[_rx][_ry] = 'R';
                board[_bx][_by] = 'B';

                dfs(num + 1, _rx, _ry, _bx, _by); // 기울이기 계속 진행

                // 백트래킹
                board[rx][ry] = 'R';
                board[bx][by] = 'B';
                board[_rx][_ry] = '.';
                board[_bx][_by] = '.';
            }
        }
        visited[rx][ry][bx][by] = false;
    }
}