백 준 - 16197

 

문제 : www.acmicpc.net/problem/16197

16197번: 두 동전

 

문제는 다음과 같습니다.

 

핵심은 2개의 동전은 같이 이동하면서 1개의 동전만이 배열에 남아있어야 문제의 조건이 만족하며 이러한 경우 중에서 최솟값을 구해야 한다는 것입니다.

또한 10번 이하에 문제의 조건을 충족하지 못하면 -1을 출력해야 합니다.

 

이동가능한 경우가 상, 화 , 좌 , 우 이고 2개의 동전이 같이 이동하므로 가능한 모든 경우를 파악하면서 이동하는 각각의 경우에 대해서 이동 횟수를 기록하기 위해 제귀를 이용해서 풀어보도록 하겠습니다.

 

전체적인 코드는 다음과 같습니다.

import java.util.*;

public class Main {

    // 문제 16197

    public static List<int[]> list = new ArrayList<>();

    public static int minValue = Integer.MAX_VALUE;

    public static int[] dx = new int[]{0 , 0 , 1, -1};
    public static int[] dy = new int[]{-1 , 1 , 0, 0};

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int n = stdin.nextInt();
        int m = stdin.nextInt();

        stdin.nextLine();

        char[][] board = new char[n][m];

        for(int i = 0 ; i < n ; i++) {

            String str = stdin.nextLine();

            for(int j = 0 ; j < str.length() ; j++) {

                char ch = str.charAt(j);

                if(ch == 'o') {

                    list.add(new int[]{i , j});
                }

                board[i][j] = ch;
            }
        }

        int[] pos1 = list.get(0);
        int[] pos2 = list.get(1);

        move(pos1[0] , pos1[1] , pos2[0] , pos2[1] , board , 0);

        if (minValue == Integer.MAX_VALUE) {

            minValue = -1;
        }

        System.out.println(minValue);

    }

    public static void move(int y1 , int x1 , int y2, int x2  , char[][] board , int idx) {

        //문제의 조건 충족 요건
        if (( (isCheck(y1 , x1 , board) == true) && (isCheck(y2 , x2, board)) == false) ||
                ( (isCheck(y1 , x1 , board) == false) && (isCheck(y2 , x2, board) == true) )) {

            minValue = Math.min(minValue , idx);


            return ;
        }

        //종료조건 1
        if (isCheck(y1 , x1 , board) == false && isCheck(y2 , x2 , board) == false) {

            return;
        }

        //종료조건 2
        if (idx >= 10) {

            return;
        }

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

            int newY1 = y1 + dy[i];
            int newX1 = x1 + dx[i];

            if (isCheck(newY1 , newX1 , board) == true) {

                if(board[newY1][newX1] == '#') {

                    newY1 = y1;
                    newX1 = x1;
                }
            }

            int newY2 = y2 + dy[i];
            int newX2 = x2 + dx[i];

            if (isCheck(newY2 , newX2 , board) == true) {

                if(board[newY2][newX2] == '#') {

                    newY2 = y2;
                    newX2 = x2;
                }
            }


            move(newY1 , newX1 , newY2 , newX2 , board , idx+1);

        }
    }

    public static boolean isCheck(int y1 , int x1 , char[][] board) {

        if ( (y1 < board.length && y1 >=0) && (x1 < board[0].length && x1 >=0)) {

            return true;
        }

        return false;
    }
}