백준 16197(JAVA)

문제

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

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

동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

풀이

최소를 보자마자 bfs로 풀어야한다고 생각했다.
그리고 두 동전의 움직임 한번에 같은 방향으로 움직이고, 두 동전은 각각 자신만의 방문처리 로직이 있어야한다고 생각했다.
다른 문제와 다른것은 두개의 동전이 움직인 다는 것이다.(그러나 한번데 같은 방향으로 움직이고, 서로 동전들은 움직임에 관여하지 않으므로 딱히 중요하진 않다.)

풀면서 고려해야할 조건

1. 갈 곳이 벽인지
2. 갈곳이 낭떠러지인지
3. 방문했는지

위 세개의 조건에 따라 움직임이 영향이 간다. 이외의에는 모두 갈수있다.

방문처리 배열은 4차원배열로 방문처리하였다.

코드

package baekjoon.그래프탐색;

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

public class Main16197_3 {
    static int N, M;
    static char[][] board;
    static boolean[][][][] visited;
    static List<Coin> coins = new ArrayList<>(); // 최초 코인의 위치
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result = -100;

    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());
        board = new char[N][M];
        visited = 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(str.charAt(j) == 'o'){
                    board[i][j] = '.';
                    Coin coin = new Coin(i, j);
                    coins.add(coin);
                }else{
                    board[i][j] = str.charAt(j);
                }
            }
        }
        bfs(coins.get(0).x, coins.get(0).y, coins.get(1).x, coins.get(1).y);

        if(result == -100){
            System.out.println(-1);
        }else{
            System.out.println(result);
        }
    }
    static void bfs(int ax, int ay, int bx, int by){
        Queue<TwoCoins> q = new LinkedList<>();
        q.offer(new TwoCoins(ax, ay, bx, by, 0));
        visited[ax][ay][bx][by] = true;

        while(!q.isEmpty()){
            TwoCoins twoCoins = q.poll();
            //버튼 10번 이상 누른거면
            if(twoCoins.count >= 10) return;

            for(int i = 0; i < 4; i++){
                int nextAx = twoCoins.ax + dx[i];
                int nextAy = twoCoins.ay + dy[i];
                int nextBx = twoCoins.bx + dx[i];
                int nextBy = twoCoins.by + dy[i];

                //벽이 있다면
                if(!canMove(nextAx, nextAy)){
                    nextAx = twoCoins.ax;
                    nextAy = twoCoins.ay;
                }
                //벽이 있다면
                if(!canMove(nextBx, nextBy)){
                    nextBx = twoCoins.bx;
                    nextBy = twoCoins.by;
                }

                int fallCount = 0;
                if(nextAx < 0 || nextAx >= N || nextAy < 0 || nextAy >= M){
                    fallCount++;
                }
                if(nextBx < 0 || nextBx >= N || nextBy < 0 || nextBy >= M){
                    fallCount++;
                }

                if(fallCount == 1){
                    //하나만 떨어진다면
                    result = twoCoins.count + 1;
                    return;
                }else if(fallCount == 0){
                    //두개다 떨어지지않는다면
                    if(!visited[nextAx][nextAy][nextBx][nextBy]){
                        visited[nextAx][nextAy][nextBx][nextBy] = true;
                        q.offer(new TwoCoins(nextAx, nextAy, nextBx, nextBy, twoCoins.count + 1));
                    }
                }
            }
        }
    }
    static boolean canMove(int x, int y){
        if(x >= 0 && y >= 0 && x < N && y < M && board[x][y] == '#'){
            return false;
        }
        return true;
    }
}

class Coin{
    int x;
    int y;

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

class TwoCoins{
    int ax;
    int ay;
    int bx;
    int by;
    int count;

    public TwoCoins(int ax, int ay, int bx, int by, int count) {
        this.ax = ax;
        this.ay = ay;
        this.bx = bx;
        this.by = by;
        this.count = count;
    }
}