[JAVA] 백준 16197번: 두 동전 ( 중급1-9 ) - hard

문제

N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, 두 동전의 위치는 다르다.

버튼은 "왼쪽", "오른쪽", "위", "아래"와 같이 4가지가 있다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다.

• 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
• 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
• 그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.

두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 20)

둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다.

• o: 동전
• .: 빈 칸
• #: 벽

동전의 개수는 항상 2개이다.

출력

첫째 줄에 두 동전 중 하나만 보드에서 떨어뜨리기 위해 눌러야 하는 버튼의 최소 횟수를 출력한다. 만약, 두 동전을 떨어뜨릴 수 없거나, 버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다.

 

실수

방문 여부를 확인할 때 2차원 배열 2개로 사용하는 부분에서 실수를 하였었다.

4차원 배열 1개로 더 깔끔하게 문제를 해결하였다.

 

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

public class baekjoon16197 {
    private static int[] rowTemp = {-1, 1, 0, 0};
    private static int[] colTemp = {0, 0, -1 ,1};
    private static boolean[][][][] visit;
    private static int n;
    private static int m;
    private static Character[][] info;
    private static int maxTurn = 10;

    public static void main(String[] args) throws IOException {
//        1 2
//        oo
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        info = new Character[n][m];
        visit = new boolean[n][m][n][m];

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String temp = br.readLine();
            for (int j = 0; j < m; j++) {
                Character coinSymbol = temp.charAt(j);
                info[i][j] = coinSymbol;
                if (coinSymbol == 'o') {
                    list.add(i);
                    list.add(j);
                }
            }
        }

        Queue<CoinsPosition> queue = new LinkedList<>();
        visit[list.get(0)][list.get(1)][list.get(2)][list.get(3)] = true;
        queue.add(new CoinsPosition(list.get(0), list.get(1), list.get(2), list.get(3), 0));

        bfs16197(queue);
        System.out.println(-1);
    }

    private static void bfs16197(Queue<CoinsPosition> queue) {
        while (!queue.isEmpty()) {
            CoinsPosition coinsPosition = queue.remove();
            int coin1row = coinsPosition.coin1row;
            int coin1col = coinsPosition.coin1col;
            int coin2row = coinsPosition.coin2row;
            int coin2col = coinsPosition.coin2col;
            int turn = coinsPosition.turn;

            if (turn == maxTurn) {
                return;
            }

            for (int i = 0; i < 4; i++) {
                int nextCoin1row = coin1row + rowTemp[i];
                int nextCoin1col = coin1col + colTemp[i];
                int nextCoin2row = coin2row + rowTemp[i];
                int nextCoin2col = coin2col + colTemp[i];
                int nextTurn = turn + 1;

                int fallenNum = 0;
                if (nextCoin1row < 0 || nextCoin1row >= n || nextCoin1col < 0 || nextCoin1col >= m ) {
                    fallenNum ++;
                }
                if (nextCoin2row < 0 || nextCoin2row >= n || nextCoin2col < 0 || nextCoin2col >= m ) {
                    fallenNum ++;
                }

                if (fallenNum == 2) {
                    continue;
                } else if (fallenNum == 1) {
                    System.out.println(nextTurn);
                    System.exit(0);
                }


                if (info[nextCoin1row][nextCoin1col] == '#') {
                    nextCoin1row = coin1row;
                    nextCoin1col = coin1col;
                }
                if (info[nextCoin2row][nextCoin2col] == '#') {
                    nextCoin2row = coin2row;
                    nextCoin2col = coin2col;
                }

                if (!visit[nextCoin1row][nextCoin1col][nextCoin2row][nextCoin2col]) {
                    visit[nextCoin1row][nextCoin1col][nextCoin2row][nextCoin2col] = true;

//                    System.out.println(fallenNum);
//                    System.out.println(nextCoin1row);
//                    System.out.println(nextCoin1col);
//                    System.out.println(nextCoin2row);
//                    System.out.println(nextCoin2col);
//                    System.out.println();
                    queue.add(new CoinsPosition(nextCoin1row, nextCoin1col, nextCoin2row, nextCoin2col, nextTurn));
                }
            }
        }

    }
}

class CoinsPosition {
    int turn;
    int coin1row;
    int coin1col;
    int coin2row;
    int coin2col;

    public CoinsPosition(int coin1row, int coin1col, int coin2row, int coin2col, int turn) {
        this.coin1row = coin1row;
        this.coin1col = coin1col;
        this.coin2row = coin2row;
        this.coin2col = coin2col;
        this.turn = turn;
    }
}