[PS] 백준13460 : 구슬 탈출 2(Java)

문제

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

13460번: 구슬 탈출 2

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

13459번: 구슬 탈출

BOJ_13459 구슬 탈출의 경우에는 10번 이내로 성공할 수 있는지 없는지에 대해서만 출력하면 되는 문제.

---

풀이

최대 10번의 게임진행에 대해 BFS를 통해 풀이가 가능한 문제

접근법

첫번째 접근법

두 개의 구슬에 대해 맵 전체를 상하좌우로 기울이는 동작을 BFS를 통해 분기를 관리하려 함.

BFS를 진행하면서 나뉘는 각각의 상황에 대한 맵의 동시성 관리를 어떻게 진행해야 하는지가 어려웠던 부분으로 3차원 배열을 활용하기로 함.

풀이로는 두 가지의 Queue를 활용

• 전체 게임을 관리하기 위한 큐
• 각각의 게임 속 두 개의 공을 밀어내는 시뮬레이션을 위한 큐

초기 맵에서 상하좌우로 기울였을 때의 결과맵을 3차원 배열 포인터를 활용하여 해당 맵을 가리키는 인덱스를 큐에 추가함으로써 동시성 관리를 수행.

공을 해당방향으로 밀어내는 시뮬레이션에 대해서도 큐를 활용해서 수행.

• 주의점으로는 다음 칸에 다른 공이 있을 경우 이동하는 로직에 대해서 신경을 써주어야 함.

게임의 결과를 판단함에 있어서는 빨간 공과 파란 공에 대한 각각의 플래그를 설정하여 빠졌는지 안빠졌는지를 비교 후 빨간 공이 빠졌을 때만 성공했다고 판단.

• 해당 접근법에서 적용한 최적화로는 이전에 진행했던 방향으로는 다음 게임에서 진행하지 않는 것 정도가 있음.

 

---

두번째 접근법(최적화 완료)

첫번째 접근법의 경우 두가지의 경우 때문에 효율이 나오지 않는 풀이 라고 생각.

1. 각각의 게임상황에 따른 결과맵을 3차원 배열로 관리할 경우 메모리 부분에서 비효율적
2. 이미 게임을 진행했던 좌표에 대해서는 재탐색이 필요없지만 진행했던 점

두번째 접근법에서는 각각의 게임 분기마다 맵을 통해 결과를 저장하고 동시성을 관리하는 것이 아닌 단순하게 두 개의 공에대한 좌표값으로 BFS를 수행. (매번 BFS문제를 풀 때 맵 자체를 바꾸면서 진행했던 적이 많아서 이러한 사고를 떠올리지 못한 것 같음..)

또한 방문체크 배열을 추가로 만들어 각 좌표에 대해 기울이는 동작을 수행하고난 후 이미 진행했던 적이 있는 좌표인지 체크함으로써 불필요한 재탐색을 제거

마지막으로 이전에 진행했던 방향값을 추가함으로써 똑같은 방향으로 미는 경우를 제거

 

---

첫번째 접근법 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//BOJ_13460 구슬 탈출 2
public class Main {
    static int N, M, point, res;
    static char[][][] map;
    static int[] dx = new int[]{1,-1,0,0};
    static int[] dy = new int[]{0,0,-1,1};
    static int[] hole = new int[2];
    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());

        map = new char[1000000][N][M];
        for(int i=0; i<N; i++) {
            String input = br.readLine();
            for(int j=0; j<M; j++) {
                char idx = input.charAt(j);
                map[0][i][j] = idx;
                if(idx == 'O') {
                    hole[0] = i;
                    hole[1] = j;
                }
            }
        }

        //상하좌우로 기울일 수 있고,
        //기울였다는 가정하에 해당방향으로 구슬이 이동
        //이동이 끝나는게 기울이는 동작이 끝났다는 것.
        point = 1;

        if(bfs()) System.out.println(res);
        else System.out.println(-1);

    }

    private static boolean bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0,0,-1}); //게임 횟수, 맵 인덱스, 어느방향으로 밀었는지

        while(!q.isEmpty()) {
            int[] cur = q.poll();

            if(cur[0] == 10) continue; //종료조건

            //해당 게임횟수 및 맵에 관해 총 4번(상하좌우)의 게임 로직을 수행하고, 결과를 서로다른 인덱스에 저장 및 큐에 추가.
            for(int d=0; d<4; d++) {
                if(cur[2] == d) continue;
                boolean redFlag = false;
                boolean blueFlag = false;
                for (int i = 0; i < N; i++) {
                    map[point][i] = map[cur[1]][i].clone();
                }
                Queue<int[]> ball = new ArrayDeque<>();
                for (int i = 0; i < N; i++) { //큐에 공 담는 과정
                    for (int j = 0; j < M; j++) {
                        if (map[cur[1]][i][j] == 'R') ball.offer(new int[]{i,j,1});
                        else if (map[cur[1]][i][j] == 'B') ball.offer(new int[]{i,j,2});
                    }
                }

                while(!ball.isEmpty()) {
                    int[] curBall = ball.poll();

                    int nx = curBall[0] + dx[d];
                    int ny = curBall[1] + dy[d];
                    if(nx<0 || ny<0 || nx>=N || ny>=M) continue;

                    if(map[point][nx][ny] == '.') { //이동 가능
                        ball.offer(new int[]{nx,ny,curBall[2]});
                        map[point][nx][ny] = map[point][curBall[0]][curBall[1]];
                        map[point][curBall[0]][curBall[1]] = '.'; //기존자리 비우기
                    }
                    else if(map[point][nx][ny] == 'B' || map[point][nx][ny] == 'R') {
                        nx += dx[d];
                        ny += dy[d];
                        if(nx<0 || ny<0 || nx>=N || ny>=M) continue;
                        if(map[point][nx][ny] == '.' || map[point][nx][ny] == 'O') { //빈자리일 때만 추가하면 87% 틀렸습니다. 그 다음자리가 hole일 경우에도 추가해줘야함!.. 두개가 같이 빠질 수 있도록.
                            ball.offer(new int[]{curBall[0],curBall[1],curBall[2]}); //기존자리 한번 더 추가
                        }
                    }
                    else if(map[point][nx][ny] == 'O') {
                        if(curBall[2] == 1) redFlag = true;
                        else blueFlag = true;
                        map[point][curBall[0]][curBall[1]] = '.'; //기존자리 비우기
                    }
                }
                if(redFlag && !blueFlag) {
                    res = cur[0] + 1;
                    return true;
                }
                else if(!redFlag && !blueFlag) { //두 개의 공이 들어가지 않을 경우에만 탐색 진행.
                    q.offer(new int[]{cur[0] + 1, point++, d});
                }
            }
        }
        return false;
    }
}

두번째 접근법 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//BOJ_13460 구슬 탈출 2
public class Main {
    static class BALL { //각 게임 결과에 대한 정보를 담는 클래스
        int rx;
        int ry;
        int bx;
        int by;
        int count;
        int dist;

        public BALL(int rx, int ry, int bx, int by, int count, int dist) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.count = count;
            this.dist = dist;
        }
        public BALL() {}
    }
    static int N, M, res;
    static BALL start = new BALL();
    static char[][] map;
    static int[] dx = new int[]{1,-1,0,0};
    static int[] dy = new int[]{0,0,-1,1};
    static boolean[][][][] v = new boolean[10][10][10][10];
    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());

        map = new char[N][M];
        for(int i=0; i<N; i++) {
            String input = br.readLine();
            for(int j=0; j<M; j++) {
                char idx = input.charAt(j);
                map[i][j] = idx;
                if(idx == 'R') {
                    start.rx = i;
                    start.ry = j;
                }
                else if(idx == 'B') {
                    start.bx = i;
                    start.by = j;
                }
                else if(idx == 'O') {
                    v[i][j][i][j] = true; //두 개의 공이 모두 구멍에 빠진 경우
                }
            }
        }

        //초기화
        start.count = 0;
        start.dist = -1;
        res = -1;

        bfs();
        if(res != -1) System.out.println(res);
        else System.out.println(-1);

    }

    private static void bfs() {
        Queue<BALL> q = new ArrayDeque<>();
        q.offer(start); //시작지점 큐에 추가
        v[start.rx][start.ry][start.bx][start.by] = true;

        while(!q.isEmpty()) {
            BALL ball = q.poll();

            if(ball.count > 10) break; //게임횟수가 10번 이상되면 종료.
            if(map[ball.rx][ball.ry] == 'O' && map[ball.bx][ball.by] != 'O') { //빨간 공만 구멍에 넣을 경우
                res = ball.count;
                break;
            }

            for(int i=0; i<4; i++) { //현 좌표에 대해 4방향 탐색
                if(ball.dist == i) continue; //이전과 같은 방향일 경우는 탐색 x
                int nextRx = ball.rx;
                int nextRy = ball.ry;
                int nextBx = ball.bx;
                int nextBy = ball.by;

                while(true) { //빨간 공에 대한 시뮬레이션
                    if (map[nextRx][nextRy] != '#' && map[nextRx][nextRy] != 'O') { //진행 가능한 경우(즉. 다음지점이 . 이거나 다른 공이 있을 경우에만)
                        nextRx += dx[i];
                        nextRy += dy[i];
                    } else { //진행 불가능한 경우
                        if (map[nextRx][nextRy] == '#') { //벽이라면 이전 칸으로 대치
                            nextRx -= dx[i];
                            nextRy -= dy[i];
                        }
                        break;
                    }
                }
                while(true) { //파란 공에 대한 시뮬레이션
                    if (map[nextBx][nextBy] != '#' && map[nextBx][nextBy] != 'O') { //진행 가능한 경우
                        nextBx += dx[i];
                        nextBy += dy[i];
                    } else { //진행 불가능한 경우
                        if (map[nextBx][nextBy] == '#') { //벽이라면 이전 칸으로 대치
                            nextBx -= dx[i];
                            nextBy -= dy[i];
                        }
                        break;
                    }
                }

                if(nextRx == nextBx && nextRy == nextBy) { //구해진 두 개의 공의 좌표가 겹칠 경우
                    if(map[nextRx][nextRy] != 'O') { //빨간공이 목표지점일 경우에는
                        int redDist = Math.abs(nextRx - ball.rx) + Math.abs(nextRy - ball.ry);
                        int blueDist = Math.abs(nextBx - ball.bx) + Math.abs(nextBy - ball.by);
                        if(redDist > blueDist) { //파란공이 앞에 있어야 할 경우
                            nextRx -= dx[i];
                            nextRy -= dy[i];
                        }
                        else {
                            nextBx -= dx[i];
                            nextBy -= dy[i];
                        }
                    }
                }
                //만약 결과좌표가 탐색했었던 좌표라면 큐에 추가하지 않음.
                if(!v[nextRx][nextRy][nextBx][nextBy]) {
                    v[nextRx][nextRy][nextBx][nextBy] = true;
                    BALL b = new BALL(nextRx, nextRy, nextBx, nextBy, ball.count+1, i);
                    q.offer(b);
                }
            }
        }
    }
}

 

---

정리

제출 번호 70244713(첫번째 접근법)

이후 두번째 접근법으로 풀이

시간에서나 메모리에서나 상당히 최적화가 된 모습을 볼 수 있음.

 

늘 풀어보던 BFS문제였지만 항상 전역 맵을 가지고 갱신시키며 값을 탐색하던 풀이로만 풀어봤던지라 해당 문제처럼 오로지 이동되는 좌표로만 풀이하는 접근법은 떠올리지 못해서 시간이 굉장히 오래걸림. (애초에 3차원 배열 1000000으로 선언할 때 부터 잘못된 것 같긴했지만)

 

최적화방법을 찾아보면서 이러한 풀이방법도 있구나라는 사고확장을 할 수 있었던 문제로 굉장히 좋았던 것 같음.

 

다음부터 동시성 관리 느낌이 드는 문제일 때 한번 더 생각해보면 좋을 것 같음. (고정된 맵일 경우)

---

Refference

https://www.youtube.com/watch?v=SarTy3ZwmVo&t=722s