알고리즘 풀이 - 백준 13460(구슬 탈출 2, 완전 탐색(시뮬레이션))

 

관련글

 

완전 탐색 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

구슬을 굴려서 빨간 구슬만 구멍에 떨어뜨릴 수 있도록 최소한의 경우로 보드를 기울이는 문제

 

 

2. 풀이

 

이 문제는 시뮬레이션으로 해결했다. 시뮬레이션 문제는 실제 가능한 모든 방법을 직접 구현하여 체크해야 하는데 구현이 까다로워서 시간이 오래 걸렸다.

기본적인 아이디어는 다음과 같다.

① 최초 위치에서 동서남북 방향으로 구슬을 굴려 이동시킨다(벽에 닿거나 구멍에 떨어질 때까지).
② 구슬이 구멍으로 떨어진 경우를 체크한다.
  - 파란 구슬이 떨어진 경우 해당 방향으로 기울인 것은 답이 될 수 없으니 다음 방향으로 굴린다.
  - 빨간 구슬만 떨어진 경우 지금까지 기울인 횟수를 반환하여 출력한다.
③ 구슬 2개가 같은 위치에 안착했다면 방향에 따라 더 우선한 구슬을 고정시키고 다른 구슬의 위치를 1칸 조정한다.
④ 현재 각 구슬들의 위치가 이전에 이미 방문했던 위치가 아니라면 Queue에 넣고 다음 탐색을 지속한다.

 

우선 ①의 경우에는 while문을 사용하여 다음 이동 위치가 '#' 즉, 벽이 되기 전까지 계속 이동을 시키고 중간에 구멍이 있다면 더 이상 이동을 중지한다.

그리고 ②를 수행하여 파란 구슬이 우선 떨어졌는지 확인한 뒤 빨간 구슬을 체크한다. 어떤 경우이든지 파란 구슬이 떨어졌다면 정답이 아니기 때문이다.

③에서는 switch문을 사용하여 현재 방향에 따라 북쪽으로 이동했는데 최초에 파란 구슬이 빨간 구슬보다 더 북쪽에 있었다면 빨간 구슬을 아래로 한 칸 이동시킨다.(방향에 따라 조정)

마지막 ④의 경우는 4차원의 boolean 배열을 생성하여 이미 방문한 위치인지를 체크할 수 있도록 하였다.

 

위의 모든 과정은 BFS로 수행한다. 왜냐하면 BFS는 모든 방향으로 우선 이동시키고 Queue에 넣기 때문에 최소의 횟수로 정답을 구하는 것을 보장할 수 있기 때문이다. 코드를 통해 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static int m;
    static char[][] board;
    static Pos bead = new Pos();
    static boolean[][][][] visited;
    
    // 동서남북 이동 방향 지정
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    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());
        board = new char[n][m];
        
        for(int i=0; i < n; i++){
            String line = br.readLine();
            for(int j=0; j < line.length(); j++){
                board[i][j] = line.charAt(j);
                if(board[i][j] == 'R'){
                    bead.ry = i;
                    bead.rx = j;
                } else if(board[i][j] == 'B'){
                    bead.by = i;
                    bead.bx = j;
                }
            }
        }
        bead.move = 0;
        bfs();
        
        br.close();
    }
    
    private static void bfs(){
        visited = new boolean[n][m][n][m];
        Queue<Pos> q = new LinkedList<>();
        q.offer(bead);
        while(!q.isEmpty()){
            Pos c = q.poll();
            visited[c.ry][c.rx][c.by][c.bx] = true;
            
            // 이미 11번 이상 움직였다면 -1을 출력하고 멈춘다.
            if(c.move >= 10) {
                System.out.println(-1);
                return;
            }
            
            for(int i=0; i < 4; i++){
                // 파란색 구슬 이동
                int b_cy = c.by;
                int b_cx = c.bx;
                while(board[b_cy+dy[i]][b_cx+dx[i]] != '#'){
                    b_cy += dy[i];
                    b_cx += dx[i];
                    if(board[b_cy][b_cx] == 'O'){
                        break;
                    }
                }
                
                // 빨간색 구슬 이동
                int r_cy = c.ry;
                int r_cx = c.rx;
                while(board[r_cy+dy[i]][r_cx+dx[i]] != '#'){
                    r_cy += dy[i];
                    r_cx += dx[i];
                    if(board[r_cy][r_cx] == 'O'){
                        break;
                    }
                }
                
                // 파란구슬이 떨어진 경우.. 그 경우는 진행해선 안됨
                if(board[b_cy][b_cx] == 'O'){
                    continue;
                }
                
                // 빨간 구슬만 떨어진 경우 정답 출력 후 멈춤
                if(board[r_cy][r_cx] == 'O'){
                    System.out.println(c.move+1);
                    return;
                }
                
                // 두 구슬의 위치가 같은 경우
                if(b_cy == r_cy && b_cx == r_cx) {
                    switch(i){
                        // 동쪽으로 이동 시
                        case 0:
                            // 열 좌표가 원래 더 우측에 있었던 것을 현 위치로 고정
                            if(c.rx > c.bx){
                                b_cx -= 1;
                            } else {
                                r_cx -= 1;
                            }
                            break;
                        // 서쪽으로 이동 시
                        case 1:
                            // 열 좌표가 원래 더 왼쪽에 있었던 것을 현 위치로 고정
                            if(c.rx > c.bx){
                                r_cx += 1;
                            } else {
                                b_cx += 1;
                            }
                            break;
                        // 남쪽으로 이동 시
                        case 2:
                            // 행 좌표가 원래 더 아래쪽에 있었던 것을 현 위치로 고정
                            if(c.ry > c.by){
                                b_cy -= 1;
                            } else {
                                r_cy -= 1;
                            }
                            break;
                        // 북쪽으로 이동 시
                        case 3:
                            // 행 좌표가 원래 더 위쪽에 있었던 것을 현 위치로 고정
                            if(c.ry > c.by){
                                r_cy += 1;
                            } else {
                                b_cy += 1;
                            }
                            break;
                    }
                } // End of Switch
                
                if(!visited[r_cy][r_cx][b_cy][b_cx]){
                    q.offer(new Pos(r_cy, r_cx, b_cy, b_cx, c.move+1));
                }
            } // End of for
        } // End of while
        System.out.println(-1);
    }
}

class Pos{
    int ry;
    int rx;
    int by;
    int bx;
    int move;
    
    public Pos(){
    }
    public Pos(int ry, int rx, int by, int bx, int move){
        this.ry=ry;
        this.rx=rx;
        this.by=by;
        this.bx=bx;
        this.move=move;
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.