[BOJ_16197] 두 동전 (java)

문제링크

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

16197번: 두 동전

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트포스, 재귀

문제는 두 동전을 보드판에 올려놓고 상하좌우 중 한 곳으로 이동시켜 주어 하나의 동전만 떨어뜨리는 방법을 구하는 문제이다.

단, 동전이 움직일 때 벽을 만나게 되면 움직이지 못하며, 그 외의 경우에는 모두 움직여 줄 수 있다. 떨어지는 경우는 동전이 보드의 배열 밖으로 나가는(범위를 벗어나는) 경우가 된다.

 

이 문제를 브루트포스로 풀 수있다고 확신을 한 핵심은 10번보다 많이 눌러야 하면 수행을 못하는 것으로 판단하기 때문이다.  따라서 최대 10번만 움직일 수있다. 경우의 수를 고려하면 상,하,좌,우 4방향으로 10번만 움직이기 때문에 $4^10$이 된다. 약 100만정도의 경우의 수이기 때문에 1초안에 문제를 해결하는데 큰 문제가 없어서 브루트포스로 모든 경우의 수를 조사해서 문제를 해결할 수 있다.

 

재귀로  모든 경우의수를 확인해줄 때 중요한 것은 몇번 옮겨졌는지와 현재 동전의 위치는 어디인지 이다.

재귀메소드의 종료 조건은 두 동전의 위치와 현재 옮겨진 횟수로 정해지기 때문이다. 만약 한개의 동전만 떨어졌다면 현재 얼마나 옮겼는지를 출력하면 되고, 동전이 두개가 동시에 떨어지거나,  두 동전의 위치가 같아지거나(같으면 어짜피 동시에 떨어지므로),10번이상 옮겨지는 경우는 옮길 수 없음을 표시해주어 종료해주면 된다.

 

재귀를 돌리는 방법은 상,하,좌,우로 벽이 아니라면 옮겨주고 확인하는 방법으로 실행해주면 된다.

구현코드

package boj_16197;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] board = new char[n][m];
        int[][] coins = new int[2][2];

        int coinCheck = 0;
        for(int i = 0; i < n; i++){
            String input = sc.next();
            for(int j = 0; j < m; j++){
                board[i][j] = input.charAt(j);
                if(input.charAt(j) =='o'){
                    coins[coinCheck][0] = i;
                    coins[coinCheck][1] = j;
                    coinCheck++;
                }
            }
        }
        if(coinCheck == 2) {
            int resultValue = moveCoin(board, coins, 0);
            if (resultValue == Integer.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(resultValue);
            }
        }
        else
            System.out.println(-1);
    }

    public static int moveCoin(char[][] board, int[][] coins, int cnt){
        if(coins[0][0] < 0 || coins[0][0] >= board.length || coins[0][1] < 0 || coins[0][1] >= board[0].length){
            if(coins[1][0] < 0 || coins[1][0] >= board.length || coins[1][1] < 0 || coins[1][1] >= board[0].length)
                return -1;
            return cnt;
        }
        if(coins[1][0] < 0 || coins[1][0] >= board.length || coins[1][1] < 0 || coins[1][1] >= board[0].length){
            return cnt;
        }
        if(cnt == 10 || (coins[0][0] == coins[1][0] && coins[0][1] == coins[1][1])){
            return -1;
        }
        // 0 : 북 1 : 동 2 : 남 3 : 서 시계방향
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};

        int min = Integer.MAX_VALUE;
        for(int i = 0; i < 4; i++){
            boolean coinOneMove = true;
            boolean coinTwoMove = true;
            coins[0][0] += dx[i];
            coins[0][1] += dy[i];
            coins[1][0] += dx[i];
            coins[1][1] += dy[i];

            if(!(coins[0][0] < 0 || coins[0][0] >= board.length || coins[0][1] < 0 || coins[0][1] >= board[0].length)
                    && board[coins[0][0]][coins[0][1]] == '#'){
                coinOneMove = false;
                coins[0][0] -= dx[i];
                coins[0][1] -= dy[i];
            }
            if(!(coins[1][0] < 0 || coins[1][0] >= board.length || coins[1][1] < 0 || coins[1][1] >= board[0].length)
                    && board[coins[1][0]][coins[1][1]] == '#'){
                coinTwoMove = false;
                coins[1][0] -= dx[i];
                coins[1][1] -= dy[i];
            }

            int value = moveCoin(board, coins, cnt + 1);
            if(value != -1){
                min = Math.min(value,min);
            }
            if(coinOneMove) {
                coins[0][0] -= dx[i];
                coins[0][1] -= dy[i];
            }
            if(coinTwoMove) {
                coins[1][0] -= dx[i];
                coins[1][1] -= dy[i];
            }
        }
        return min;
    }
}

 

시간복잡도

시간복잡도는 경우의 수를 고려하여 $O(4^n)$이라고 할 수 있다.

n : 이동하는 횟수 (1 <= n <= 10)

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)