[BOJ] 13459. 구슬 탈출(시뮬레이션, BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

 

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

해결하는데 시간이 꽤 걸렸던 문제다..

생각보다 처리해줘야 할 부분들이 많았다ㅠㅠ

우선 문제를 정리해보자.

*. 빨간 구슬을 구멍을 통해서 빼내는 것. 이때, 파란 구슬이 구멍에서 빠지면 안 된다.

*. 각각의 동작에서 공은 동시에 움직인다.

*. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.

빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 

*. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.

이제 로직을 생각해보자.

1. 한 턴에서 빨간 구슬과 파란 구슬을 동시에 움직인다.

빨간 구슬과 파란 구슬이 같은 칸에 있을 수 없다는 조건을 비롯하여

기우는 방향과 각 구슬의 위치에 따라 조건을 동시에 처리해주어야 해서 

한 턴에서의 빨간 구슬과 파란 구슬을 동시에 관리해주어야 한다.

처음에 빨간 구슬과 파란 구슬을 따로 관리해주었더니 많이 꼬였었다..

    static class Turn {
        int rdr, rdc, blr, blc;
 
        public Turn(int rdr, int rdc, int blr, int blc) {
            this.rdr = rdr;
            this.rdc = rdc;
            this.blr = blr;
            this.blc = blc;
        }
    }

또한, 이미 확인한 구슬의 상태를 체크해주기 위해서 상태를 관리해야하는데 4차원 상태 배열을 사용했다.

각 구슬이 아래와 같은 상태일 때 이미 확인했다는 것을 체크해준다.

[빨강행][빨강열][파랑행][파랑열]

2. 4방으로 장난감을 기울여보자.

바깥 행과 열은 모두 벽으로 막혀있으므로 범위를 체크해줄 필요는 없다.

다음 좌표가 벽이 아니고 현재 좌표가 구멍이 아니라면 계속 구슬을 이동시켜준다.

(현재 좌표가 구멍이라면 구슬이 빠지게 되므로)

여기서 이동한 거리도 계산해주는데,

빨간 구슬과 파란 구슬이 같은 칸에 있을 경우를 처리해주기 위함이다.

구슬이 동시에 같은 칸에 있을 경우 어떻게 처리할지 많은 시도를 해보았는데..

이 방법이 가장 깔끔한 것 같다.

    private static Marble move(int r, int c, int dist, int d) {
 
        int rr = r, cc = c;
        // 다음 칸이 벽이 아니고, 현재 칸이 구멍이 아니라면 계속 이동
        while(map[rr + dr[d]][cc + dc[d]] != '#' && map[rr][cc] != 'O') {
            rr += dr[d];
            cc += dc[d];
            dist++;
        }
        
        return new Marble(rr, cc, dist);
    }

3. 구슬이 동시에 같은 칸에 있을 경우

구슬이 기울여진 방향으로 이동하면서 구해진 이동 거리를 이용하자.

더 많이 이동한 구슬은 이전 위치를 한 칸 돌려주자!

    // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
        // 빨간 구슬이 더 많이 이동했을 경우
        if(nRed.dist> nBlue.dist) {
            // 이전 위치로
            nRed.r -= dr[d];
            nRed.c -= dc[d];
        } else {
            nBlue.r -= dr[d];
            nBlue.c -= dc[d];
        }
    }

+.

요즘 문제가 잘 풀린다고 문제를 읽자마자 코딩을 시작한다..

다행히 이 문제를 통해 다시 깨달음을 얻게 되었다..

아래 3, 4 단계를 좀 지키자~~~!

3. Create solution plan (select Algorithm, Data structure)

4. Prove the plan (check performance time and usage memory)

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ13459 {
 
    static int N, M;
    static char[][] map;
    static boolean[][][][] visited; // 빨강, 파랑 구슬의 visit 상태
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    
    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()); // Row
        M = Integer.parseInt(st.nextToken()); // Column
        map = new char[N][M]; 
        visited = new boolean[N][M][N][M]; 
        
        int rdr, rdc, blr, blc;
        rdr = rdc = blr = blc = 0;
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 'R') {
                    rdr = i; rdc = j;
                }
                else if(map[i][j] == 'B') {
                    blr = i; blc = j;
                }
            }
        }
        
        System.out.println(process(rdr, rdc, blr, blc));
    }
 
    private static int process(int rdr, int rdc, int blr, int blc) {
        
        Queue<Turn> q = new LinkedList<>();
        int time = 1;
        
        q.add(new Turn(rdr, rdc, blr, blc));
        visited[rdr][rdc][blr][blc] = true;
        
        Marble nRed = null, nBlue = null;
        while(!q.isEmpty()) {
            
            int size = q.size();
            while(size-- > 0) {
                Turn now = q.poll();
                
                // 4방으로 장난감을 기울여보자.
                for (int d = 0; d < 4; d++) {
                    // 빨간 구슬 이동
                    nRed = move(now.rdr, now.rdc, 0, d);
                    // 파랑 구슬 이동
                    nBlue = move(now.blr, now.blc, 0, d);
                    
                    // 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패
                    if(map[nBlue.r][nBlue.c] == 'O') continue;
                    // 빨간 구슬만 구멍에 빠질 경우
                    if(map[nRed.r][nRed.c] == 'O') return 1;
                    
                    // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
                    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
                        // 빨간 구슬이 더 많이 이동했을 경우
                        if(nRed.dist> nBlue.dist) {
                            // 이전 위치로
                            nRed.r -= dr[d];    
                            nRed.c -= dc[d];
                        } else {
                            nBlue.r -= dr[d];
                            nBlue.c -= dc[d];
                        }
                    }
 
                    // 이미 시도해봤던 상태라면 pass
                    if(visited[nRed.r][nRed.c][nBlue.r][nBlue.c]) continue;
                    
                    visited[nRed.r][nRed.c][nBlue.r][nBlue.c] = true;
                    
                    // Queue에 추가
                    q.add(new Turn(nRed.r, nRed.c, nBlue.r, nBlue.c));
                }
            }
    
            // 10번 이하로 성공할 수 없다면
            if(++time > 10) return 0;
        }
        return 0;
    }
 
    private static Marble move(int r, int c, int dist, int d) {
 
        int rr = r, cc = c;
        // 다음 칸이 벽이 아니고, 현재 칸이 구멍이 아니라면 계속 이동
        while(map[rr + dr[d]][cc + dc[d]] != '#' && map[rr][cc] != 'O') {
            rr += dr[d];
            cc += dc[d];
            dist++;
        }
        
        return new Marble(rr, cc, dist);
    }
 
    static class Marble {
        int r, c, dist;
 
        public Marble(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
        
    }
    
    static class Turn {
        int rdr, rdc, blr, blc;
 
        public Turn(int rdr, int rdc, int blr, int blc) {
            this.rdr = rdr;
            this.rdc = rdc;
            this.blr = blr;
            this.blc = blc;
        }
    }
}
 

---

#. Problem

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

* The copyright in this matter is in BOJ

거의.. 동일한 문제다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ13460 {
 
    static int N, M;
    static char[][] map;
    static boolean[][][][] visited; // 빨강, 파랑 구슬의 visit 상태
    static int[] dr = {-1, 0, 1, 0}, dc = {0, 1, 0, -1};
    
    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()); // Row
        M = Integer.parseInt(st.nextToken()); // Column
        map = new char[N][M]; 
        visited = new boolean[N][M][N][M]; 
        
        int rdr, rdc, blr, blc;
        rdr = rdc = blr = blc = 0;
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 'R') {
                    rdr = i; rdc = j;
                }
                else if(map[i][j] == 'B') {
                    blr = i; blc = j;
                }
            }
        }
        
        System.out.println(process(rdr, rdc, blr, blc));
    }
 
    private static int process(int rdr, int rdc, int blr, int blc) {
        
        Queue<Turn> q = new LinkedList<>();
        int time = 1;
        
        q.add(new Turn(rdr, rdc, blr, blc));
        visited[rdr][rdc][blr][blc] = true;
        
        Marble nRed = null, nBlue = null;
        while(!q.isEmpty()) {
            
            int size = q.size();
            while(size-- > 0) {
                Turn now = q.poll();
                
                // 4방으로 장난감을 기울여보자.
                for (int d = 0; d < 4; d++) {
                    // 빨간 구슬 이동
                    nRed = move(now.rdr, now.rdc, 0, d);
                    // 파랑 구슬 이동
                    nBlue = move(now.blr, now.blc, 0, d);
                    
                    // 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패
                    if(map[nBlue.r][nBlue.c] == 'O') continue;
                    // 빨간 구슬만 구멍에 빠질 경우
                    if(map[nRed.r][nRed.c] == 'O') return time;
                    
                    // 빨간 구슬과 파란 구슬이 같은 칸에 있을 경우
                    if (nRed.r == nBlue.r && nRed.c == nBlue.c) {
                        // 빨간 구슬이 더 많이 이동했을 경우
                        if(nRed.dist> nBlue.dist) {
                            // 이전 위치로
                            nRed.r -= dr[d];    
                            nRed.c -= dc[d];
                        } else {
                            nBlue.r -= dr[d];
                            nBlue.c -= dc[d];
                        }
                    }
 
                    // 이미 시도해봤던 상태라면 pass
                    if(visited[nRed.r][nRed.c][nBlue.r][nBlue.c]) continue;
                    
                    visited[nRed.r][nRed.c][nBlue.r][nBlue.c] = true;
                    
                    // Queue에 추가
                    q.add(new Turn(nRed.r, nRed.c, nBlue.r, nBlue.c));
                }
            }
    
            // 10번 이하로 성공할 수 없다면
            if(++time > 10) return -1;
        }
        return -1;
    }
 
    private static Marble move(int r, int c, int dist, int d) {
 
        int rr = r, cc = c;
        // 다음 칸이 벽이 아니고, 현재 칸이 구멍이 아니라면 계속 이동
        while(map[rr + dr[d]][cc + dc[d]] != '#' && map[rr][cc] != 'O') {
            rr += dr[d];
            cc += dc[d];
            dist++;
        }
        
        return new Marble(rr, cc, dist);
    }
 
    static class Marble {
        int r, c, dist;
 
        public Marble(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }
        
    }
    
    static class Turn {
        int rdr, rdc, blr, blc;
 
        public Turn(int rdr, int rdc, int blr, int blc) {
            this.rdr = rdr;
            this.rdc = rdc;
            this.blr = blr;
            this.blc = blc;
        }
    }
}