[백준] 13460번 구슬 탈출2(java)

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

13460번: 구슬 탈출 2

조금 난도가 있는 bfs 문제이다.

 

핵심

중요하다고 생각하는 부분은 빨간 구슬과 파란 구슬이 움직일 때 둘의 위치에 따라 먼저 움직이는 순서가 달라져야 한다는 것이다.

만약.. RB가 있을 때 왼쪽으로 움직인다면 R -> B순으로 움직여야 한다.

 

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static String[][] map;
    static boolean[][][][] visited;
    static String[][] copyMap;
    static int N;
    static int M;
    static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public static void main(String[] args) {
        init();
        System.out.println(bfs());
    }

    private static void init() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new String[N][M];
        visited = new boolean[N][M][N][M];
        copyMap = new String[N][M];

        for (int i = 0; i < N; i++) {
            String[] row = sc.next().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = row[j];
            }
        }
    }

    private static int[] findIndex(String target) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j].equals(target)) {
                    map[i][j] = ".";
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }

    private static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        int[] redIndex = findIndex("R");
        int[] blueIndex = findIndex("B");

        q.offer(new int[]{redIndex[0], redIndex[1], blueIndex[0], blueIndex[1], 1});
        visited[redIndex[0]][redIndex[1]][blueIndex[0]][blueIndex[1]] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int redY = now[0];
            int redX = now[1];
            int blueY = now[2];
            int blueX = now[3];
            int count = now[4];

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

            for (int i = 0; i < 4; i++) {
                cloneMap();

                int[] moveRedIndex;
                int[] moveBlueIndex;

                if ((i == 0 && redY > blueY) || (i == 1 && redY <= blueY)) {
                    moveRedIndex = moveMarble(redY, redX, i, "R");
                    moveBlueIndex = moveMarble(blueY, blueX, i, "B");
                } else if ((i == 2 && redX > blueX) || (i == 3 && redX <= blueX)) {
                    moveRedIndex = moveMarble(redY, redX, i, "R");
                    moveBlueIndex = moveMarble(blueY, blueX, i, "B");
                } else {
                    moveBlueIndex = moveMarble(blueY, blueX, i, "B");
                    moveRedIndex = moveMarble(redY, redX, i, "R");
                }

                if (isGameOver(moveBlueIndex)) {
                    continue;
                } else if (isWon(moveRedIndex)) {
                    return count;
                }

                if (!visited[moveRedIndex[0]][moveRedIndex[1]][moveBlueIndex[0]][moveBlueIndex[1]]) {
                    q.offer(new int[]{moveRedIndex[0], moveRedIndex[1], moveBlueIndex[0], moveBlueIndex[1], count + 1});
                    visited[moveRedIndex[0]][moveRedIndex[1]][moveBlueIndex[0]][moveBlueIndex[1]] = true;
                }
            }
        }
        return -1;
    }

    private static void cloneMap() {
        for (int k = 0; k < map.length; k++) {
            copyMap[k] = map[k].clone();
        }
    }

    private static int[] moveMarble(int y, int x, int directionIndex, String color) {
        int dy = move[directionIndex][0];
        int dx = move[directionIndex][1];

        while (isValidMove(y + dy, x + dx)) {
            y += dy;
            x += dx;
            if (map[y][x].equals("O")) {
                return new int[]{0, 0};
            }
        }
        copyMap[y][x] = color;
        return new int[]{y, x};
    }

    private static boolean isValidMove(int y, int x) {
        String cell = copyMap[y][x];
        return (!cell.equals("#") && !cell.equals("R") && !cell.equals("B"));
    }

    private static boolean isGameOver(int[] blueIndex) {
        return blueIndex[0] == 0;
    }

    private static boolean isWon(int[] redIndex) {
        return redIndex[0] == 0;
    }
}

해설

우선 map을 초기화시켜 준다. -> 이때 맵은 장애물과 이동가능한 길 구멍뿐이다.

이후에 처음 빨간 구슬과 파란 구슬의 위치를 찾아서 사용한다.

Queue에는 빨간 구슬의 위치와 파란 구슬의 위치, 움직인 카운트를 저장해 둔다.

또한 한번 이동했던 위치는 다시 탐색하지 않는다. 

중요한 점은 cloneMap을 사용하였다. 물론 다른 방법도 존재하지만, 나는 순수한 맵을 사용하기 위해 clone을 사용하였다.

-> 구슬은 그때그때 위치만 넣어주기 위함

기울이는 방향에서 앞선 구슬을 먼저 이동시켜 준다. ex) 빨간 공 이후 파란 공 

기울일 때 #이나 다른 구슬이 없을 때까지 움직인다. 하지만 만약 구멍을 만난다면 [0,0]을 리턴해준다.

이후 만약 파란 공의 좌표가 0이 나왔다면 -1 이후의 움직임을 멈춘다.(continue)

반대로 빨간 공만 좌표가 0 -> 구멍을 통과 -> 카운트를 리턴해준다.

만약 두 공 전부 구멍을 통과하지 않았다면 Queue에 다음 좌표를 넣어준다.

 

 

배운 점

아이디어 자체는 생각보다 쉽게 할 수 있었다.

다만 아쉬운 점은 로직자체를 좀 더 이쁘게 하고 싶었지만 생각보다 문제 구현이 힘들어서 더러워진 느낌이 있다.

또한 중간에 clone 부분에서 실수를 하였다.

1차원 배열의 경우 단순하게 clone을 해주면 깊은 복사를 하지만 2차원 배열의 경우 행마다 clone을 해주어야 한다.

이것을 놓치고 있어서 디버깅에 시간이 많이 걸렸다.

오랜만에 백준도 풀게 되었는데, 백준도 재미있는 문제가 많은 것 같다.

요즘 알고리즘 푸는 것이 너무 재미있다고 생각된다.

어쩌다 보니 리트 코드, 백준, 프로그래머스 골고루 풀게 되었다..