[BaekJoon] 13460번 구슬 탈출 2 (Java) 문제 풀이 [Gold 1]

문제

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

13460번: 구슬 탈출 2

 

어떻게 풀 것인가?

문제를 읽었을 때 2차원 배열이 보이고 탈출 구멍에 따라 빨간 구슬이 먼저 와야하며, 최소한적으로 판을 흔들어야한다고 했을때는 BFS 문제이구나 싶었지만, 구현이 가미된 BFS였다.

 

구현은 어렵다. 단순 정답이 정해진 것이 아니라 정말 생각한 것을 프로그래밍으로 구현할 수 있냐? 라는 것을 묻기에 더 그런 것 같다.

 

처음에는 빨간 구슬과 파란 구슬을 따로 움직여야한다고 생각했다. 그렇게 하다보니 로직이 너무 복잡해져서 풀기에 너무 까다롭고, 코드가 번잡해졌다. 그리고 무엇보다 정답보다는 조금 더 쉽게 볼 수 있는  코드가 필요하다고 생각했다.

 

다행히 나와 풀이는 비슷하지만 빨간 구슬과 파란 구슬을 같이 생각하여 class로 묶어서 푸신 분이 있었다. 그 분의 코드를 받아서 내 코드를 수정했다.

 

이 문제는 BFS를 수행해서 최단거리로 탈출한다. <- 이 부분은 다행히 단순 BFS 문제이다.

 

다만 위에서도 언급했듯이 방문 확인을 해야하는데, 빨간 구슬과 파란 구슬을 같이 움직여야함으로 visit함수도 4차원으로 선언하여 기록해야한다.

 

풀면서 놓쳤던점

빨간 구슬과 파란 구슬을 따로 생각한 것

 

이 문제를 통해 얻어갈 것

구현, 시뮬레이션에서 BFS를 사용

 

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 백준알고리즘 13460번 구슬 탈출 2
class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Marble {
    int rx;
    int ry;
    int bx;
    int by;
    int cnt;

    Marble(int rx, int ry, int bx, int by, int cnt) {
        this.rx = rx;
        this.ry = ry;
        this.bx = bx;
        this.by = by;
        this.cnt = cnt;
    }
}

public class Main {
    static int N, M;
    static char[][] arr;
    static Point hole;
    static boolean[][][][] visit;
    static Marble blue, red;

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {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());
        M = Integer.parseInt(st.nextToken());
        arr = new char[N][M];
        visit = new boolean[N][M][N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                if ('O' == str.charAt(j)) { // 구멍의 위치를 체크
                    hole = new Point(i, j);
                } else if (str.charAt(j) == 'B') {
                    blue = new Marble(0, 0, i, j, 0);
                } else if (str.charAt(j) == 'R') {
                    red = new Marble(i, j, 0, 0, 0);
                }
                arr[i][j] = str.charAt(j);
            }
        }
        System.out.println(BFS());
    }

    public static int BFS() {
        Queue<Marble> queue = new LinkedList<>();
        queue.add(new Marble(red.rx, red.ry, blue.bx, blue.by, 1));
        visit[red.rx][red.ry][blue.rx][blue.ry] = true;

        while (!queue.isEmpty()) {
            Marble marble = queue.poll();

            int curRx = marble.rx;
            int curRy = marble.ry;
            int curBx = marble.bx;
            int curBy = marble.by;
            int curCnt = marble.cnt;

            if (curCnt > 10) {
                return -1;
            }

            for (int i = 0; i < 4; i++) {
                int newRx = curRx;
                int newRy = curRy;
                int newBx = curBx;
                int newBy = curBy;

                boolean isRedHole = false;
                boolean isBlueHole = false;

                while (arr[newRx + dx[i]][newRy + dy[i]] != '#') {
                    newRx += dx[i];
                    newRy += dy[i];

                    if (newRx == hole.x && newRy == hole.y) {
                        isRedHole = true;
                        break;
                    }
                }

                while (arr[newBx + dx[i]][newBy + dy[i]] != '#') {
                    newBx += dx[i];
                    newBy += dy[i];

                    if (newBx == hole.x && newBy == hole.y) {
                        isBlueHole = true;
                        break;
                    }
                }

                if (isBlueHole) {
                    continue;
                }

                if (isRedHole && !isBlueHole) {
                    return curCnt;
                }


                if (newRx == newBx && newRy == newBy) {
                    if (i == 0) {

                        if (curRx > curBx) newRx -= dx[i];
                        else newBx -= dx[i];
                    } else if (i == 1) {
                        if (curRy < curBy) newRy -= dy[i];
                        else newBy -= dy[i];
                    } else if (i == 2) {
                        if (curRx < curBx) newRx -= dx[i];
                        else newBx -= dx[i];
                    } else {
                        if (curRy > curBy) newRy -= dy[i];
                        else newBy -= dy[i];
                    }
                }

                if (!visit[newRx][newRy][newBx][newBy]) {
                    visit[newRx][newRy][newBx][newBy] = true;
                    queue.add(new Marble(newRx, newRy, newBx, newBy, curCnt + 1));
                }
            }
        }
        return -1;
    }

}

 

참고

https://minhamina.tistory.com/191

[백준 - Java] 13460번 : 구슬 탈출 2 (삼성SW역량테스트 기출 문제)