[JAVA] 백준 16197번: 두 동전

 

문제

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

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

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

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

입력

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

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

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

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

출력

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

 

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

public class baekjoon16197 {
    static int[] aryH = {0, 0, -1, 1};    
    static int[] aryW = {-1, 1, 0, 0};
    static int n;
    static int m;
    static int res = -1;
    static String[][] info;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        int h1 = 0;
        int w1 = 0;
        int h2 = 0;
        int w2 = 0;
        boolean firstCoin = true;
        boolean[][][] visit = new boolean[n][m][2];
        info = new String[n][m];
        for (int i = 0; i < n; i++) {
            String[] tempAry = sc.next().split("");
            for (int j = 0; j < tempAry.length; j++) {
                info[i][j] = tempAry[j];
                if (tempAry[j].equals("o") && firstCoin) {
                    h1 = i;
                    w1 = j;
                    firstCoin = false;
                } else if (tempAry[j].equals("o") && !firstCoin) {
                    h2 = i;
                    w2 = j;
                }
            }
        }

        

         
        coinTracking(new CoinPosition(h1, w1, h2, w2), 1);
        System.out.println(res);
        
    }
    static void coinTracking(CoinPosition cp, int cnt){                 
        int curH1 = cp.h1;
        int curW1 = cp.w1;
        int curH2 = cp.h2;
        int curW2 = cp.w2;
        if (cnt > 10) {
            return;
        }

        for (int i = 0; i < 4; i++) {
            int canFall = 0;
            int nextH1 = curH1 + aryH[i];
            int nextW1 = curW1 + aryW[i];
            int nextH2 = curH2 + aryH[i];
            int nextW2 = curW2 + aryW[i];
            
            // 첫번째 코인이 떨어지는 경우
            if (nextH1 < 0 || nextH1 >= n || nextW1 < 0 || nextW1 >= m) {
                canFall++;
            } else if (info[nextH1][nextW1].equals("#")) {
                nextH1 = curH1;
                nextW1 = curW1;
            }
            // 두번째 코인이 떨어지는 경우
            if (nextH2 < 0 || nextH2 >= n || nextW2 < 0 || nextW2 >= m) {
                canFall++;
            } else if (info[nextH2][nextW2].equals("#")) {
                nextH2 = curH2;
                nextW2 = curW2;
            }

            // 하나만 떨어진 경우
            if (canFall == 1) {
                if (res == -1) {
                    res = cnt;
                } else {
                    res = Math.min(res, cnt);
                }                
            } else if (canFall == 0) {
                coinTracking(new CoinPosition(nextH1, nextW1, nextH2, nextW2), cnt+1);
            }                                   
        }

        
    }
}

class CoinPosition{
    int h1;
    int w1;
    int h2;
    int w2;
    CoinPosition(int h1, int w1, int h2, int w2) {
        this.h1 = h1;        
        this.w1 = w1;
        this.h2 = h2;
        this.w2 = w2;
    }
}

 

 

https://maivve.tistory.com/247

(JAVA) 백준 16197번 : 두 동전 --- [백트래킹]