[JAVA/BFS,구현] 백준 13460 구슬 탈출 2

1. 문제

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

13460번: 구슬 탈출 2

 

2. 풀이

가장 빠른 횟수를 구하기 위해 BFS를 사용한다.

• 구슬이 굴러가면 파란 구슬과 빨간 구슬이 같이 굴러가게 되므로, 두 구슬의 위치를 모두 담은 클래스를 선언해 사용한다.
• 맨 처음 구슬의 위치를 저장해 BFS를 시작한다.
  • 구슬들의 위치 방문여부를 확인하기 위해 4차원 배열을 사용한다.(visited[n][m][n][m])
  • 4 방향으로 빨강, 파랑 구슬을 각각 굴려가며 벽이나 구멍을 만날 때까지 이동한다
    • 구슬이 구멍을 지났을 때, 파란 구슬이면 실패한 케이스이므로 탐색을 종료한다. 빨간 구슬이면 이때까지 걸린 횟수를 계산해 출력한 후 종료한다.
    • 판(?)의 사방은 벽으로 둘러쌓여 있으므로 범위 계산을 따로 해 줄 필욘 없다.
  • 위에서 이동 할 때 구슬 겹침을 고려하지 않았으므로, 구슬이 겹칠 경우 위치를 조정한다.
• 10번 이상 횟수가 진행될 경우 -1을 출력한다.

+) 세세한 조건 구성에서 되게 많이 틀렸다.... 다시 풀어보자....

 

3. 코드

 

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

class Points{
    int rX, rY, bX, bY, count;
    
    public Points(int rX, int rY, int bX, int bY, int count) {
        this.rX = rX;
        this.rY = rY;
        this.bX = bX;
        this.bY = bY;
        this.count = count;
    }
}

class Main{
    
    // 구슬탈출
    
    static int n, m;
    static char[][] map;
    static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    
    public static void bfs(Points now) {
        boolean[][][][] visited = new boolean[n][m][n][m]; // 방문여부 저장
        Queue<Points> q = new LinkedList<Points>();
        q.add(now);
        
        
        while(!q.isEmpty()) {
            Points points = q.poll();
            visited[points.rX][points.rY][points.bX][points.bY] = true;
            
            if(points.count >= 10) {
                System.out.println(-1);
                return;
            }
            
            for(int i = 0; i < 4; i++) {
                            
                // 빨간 구슬 이동
                int newRX = points.rX;
                int newRY = points.rY;
                while(map[newRX + dir[i][0]][newRY + dir[i][1]] != '#'){
                    newRX += dir[i][0];
                    newRY += dir[i][1];
                    if(map[newRX][newRY] == 'O') break;
                }
                
                // 파란 구슬 이동
                int newBX = points.bX;
                int newBY = points.bY;
                while(map[newBX + dir[i][0]][newBY + dir[i][1]] != '#') {
                    newBX += dir[i][0];
                    newBY += dir[i][1];
                    if(map[newBX][newBY] == 'O') break;
                }
                
                // 파란색 구슬이 구멍에 빠지면 탐색 종료
                if(map[newBX][newBY] == 'O') 
                    continue;

                // 빨간색 구슬이 구멍에 빠지면 min 출력
                if(map[newRX][newRY] == 'O' && map[newBX][newBY] != 'O') {
                    System.out.println(points.count + 1);
                    return;
                }
                
                // 두 구슬 위치가 겹치면 위치 조정
                if(newRX == newBX && newRY == newBY) {
                    switch(i) {
                    case 0: // 남
                        if(points.rX > points.bX) newBX--;
                        else newRX--;
                        break;
                    case 1: // 북
                        if(points.rX > points.bX) newRX++;
                        else newBX++;
                        break;
                    case 2: // 동
                        if(points.rY > points.bY) newBY--;
                        else newRY--;
                        break;
                    case 3: // 서
                        if(points.rY > points.bY) newRY++;
                        else newBY++;
                        break;
                    }
                }
                
                if(!visited[newRX][newRY][newBX][newBY]) {
                    q.add(new Points(newRX, newRY, newBX, newBY, points.count + 1));
                }    
            }
        }
        System.out.println("-1");
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        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 rX = 0, rY = 0, bX = 0, bY = 0;

        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') {
                    rX = i;
                    rY = j;
                } else if(map[i][j] == 'B') {
                    bX = i;
                    bY = j;
                }
            }
        }
        
        bfs(new Points(rX, rY, bX, bY, 0));
        
    }
}