[BOJ] 13460번. 구슬 탈출 2

🌱 문제 링크

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

13460번: 구슬 탈출 2

 

📝 풀이 과정

문제 유형 : BFS

 

블로그의 힘을 빌려 어찌어찌 풀긴 했는데.. BFS로 접근할 생각을 못했다. (참조: https://sdesigner.tistory.com/105)

내가 했던 접근 방법은 경우의 수가 나눠지니 완탐으로 재귀를 사용해 턴 수를 매개변수로 주고 4방을 탐색해서 구슬이 갈 수 있다면 가고 다음 턴으로 넘어가는 방식으로 접근을 했는데, 파란 공을 굴리다가 빨간 공이 만나면 어떻게 하지 등등 점점 조건이 많아지자 머리가 꼬이는 느낌이었다. 

문제 유형이 최단거리로 출구에 도착하는 것이기 때문에 BFS 로 접근할 수 있구나 싶었다.

또 4차원 배열은 처음 써보는데 앞으로도 잘 유용하게 쓸 수 있을 것 같다.

 

• Balls 클래스
  • 파란 공의 위치 (br, bc), 빨간 공의 위치(rr, rc)
  • cnt : 현재 몇 번째 기울이기 인지를 표시
• void bfs(Balls balls) 메소드
  • Queue에 현재 Balls 를 넣어 시작한다.
  • 현재 Balls 를 visited[][][][] 에 방문 표시한다. (한번 공이 있던 위치에 다시 가지 않기 위해)
  • 4 방을 탐색해서 기울였을 때 빨간 공과 파란 공의 위치를 찾는다.
  • 파란 공이 출구를 만나면 더 이상 진행하지 않고 다음 방향이나 다음 경우로 넘어간다.
  • 빨간 공이 출구를 만난다면 턴 수를 출력하고 종료한다.
  • 빨간 공과 파란 공의 위치가 같다면 위치를 조정한다.
  • 옮겨진 빨간 공과 파란 공의 위치가 방문한 적이 없는 위치라면 Que에 넣는다.
• int[] rollBall(int r, int c, int d)
  • 빨간 공과 파란 공을 d  방향으로 굴린 뒤 최종 위치를 리턴한다.

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Main_bj_13460_구슬탈출2 {
    
    static class Balls{
        int br, bc, rr, rc, cnt;        // cnt: 몇번째 턴
        
        public Balls() {}
 
        public Balls(int br, int bc, int rr, int rc, int cnt) {
            super();
            this.br = br;
            this.bc = bc;
            this.rr = rr;
            this.rc = rc;
            this.cnt = cnt;
        }
    }
    
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static int N, M, ans;
    static char[][] map;
    
    public static void main(String[] args) throws Exception{
        //System.setIn(new FileInputStream("res/input_bj_13460.txt"));
        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];
        Balls balls = new Balls();        // br, bc, rr, rc, cnt
        
        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]=='B') {
                    balls.br = i; balls.bc = j;
                }
                if(map[i][j]=='R') {
                    balls.rr = i; balls.rc = j;
                }
            }
        }
        // 입력 완료
        
        ans = -1;
        bfs(balls);
        System.out.println(ans);
        br.close();
    }
    
    static void bfs(Balls balls) {
        Queue<Balls> que = new ArrayDeque<>();
        que.offer(balls);
        boolean[][][][] visited = new boolean[10][10][10][10];        // 공의 위치에 따른 방문 처리 (한번 방문한 위치는 가지 않기 위해)
        
        stop: while(!que.isEmpty()) {
            Balls curballs = que.poll();
            visited[curballs.br][curballs.bc][curballs.rr][curballs.rc] = true;
            
            if(curballs.cnt>=10) break;        // 10번 굴렸다면 더이상 굴릴 필요가 없음
            
            for(int d=0; d<4; d++) {        // 현재 볼들에 대해서 4방 탐색
                
                // 공을 굴림
                int[] nextB = rollBall(curballs.br, curballs.bc, d);
                int[] nextR = rollBall(curballs.rr, curballs.rc, d);
                
                if(map[nextB[0]][nextB[1]] == 'O') continue;
                if(map[nextR[0]][nextR[1]] == 'O') {
                    ans = curballs.cnt+1; break stop;
                }
                
                // 두 공의 위치가 같다면
                if(nextB[0] == nextR[0] && nextB[1] == nextR[1]) {
                    if(d==0) {
                        if(curballs.br < curballs.rr) {
                            nextR[0]++;
                        }else {
                            nextB[0]++;
                        }
                    }else if(d==1) {
                        if(curballs.bc > curballs.rc) {
                            nextR[1]--;
                        }else {
                            nextB[1]--;
                        }
                    }else if(d==2) {
                        if(curballs.br > curballs.rr) {
                            nextR[0]--;
                        }else {
                            nextB[0]--;
                        }
                    }else {
                        if(curballs.bc < curballs.rc) {
                            nextR[1]++;
                        }else {
                            nextB[1]++;
                        }
                    }
                }
                // 공 위치 조정 완료
                
                if(!visited[nextB[0]][nextB[1]][nextR[0]][nextR[1]]) {    // 처음 가보는 위치라면
                    que.offer(new Balls(nextB[0], nextB[1], nextR[0], nextR[1], curballs.cnt+1));
                }
                
            }
            
        }
        
    }
    
    static int[] rollBall(int r, int c, int d) {
        
        while(map[r][c]!='#') {      // 사방이 벽이여서 범위 검사 하지 않아도 됨
            if(map[r][c]=='O') return new int[] {r, c};        // 현재 위치가 탈출구라면 현재 위치를 리턴
            
            r += dr[d];
            c += dc[d];
        }
        
        // 벽을 만나서 while 문을 빠져 나온 경우, 벽 이전의 위치를 리턴
        return new int[] {r-=dr[d], c-=dc[d]};
    }
}
 

 

📌 채점 결과