문제

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

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

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

입력

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

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

• o: 동전
• .: 빈 칸
• #: 벽
  동전의 개수는 항상 2개이다.

출력

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

예제1 - 입력

1 2
oo

예제1 - 출력

1

예제2 - 입력

6 2
.#
.#
.#
o#
o#
##

예제2 - 출력

4

예제3 - 입력

6 2
..
..
..
o#
o#
##

예제3 - 출력

3

예제4 - 입력

5 3
###
.o.
###
.o.
###

예제4 - 출력

-1

예제4 - 입력

5 3
###
.o.
#.#
.o.
###

예제4 - 출력

3

제출 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n =  Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        Pair coin1 = null, coin2 = null;
        for (int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'o') {
                    if (coin1 == null)
                        coin1 = new Pair(i, j);
                    else
                        coin2 = new Pair(i, j);
                }
            }
        }
        br.close();

        int[] mx = {1, -1, 0, 0};
        int[] my = {0, 0, 1, -1};

        Queue<Pair[]> queue = new LinkedList<>();
        Pair[] now = {coin1, coin2};
        visited[now[0].x][now[0].y][now[1].x][now[1].y] = 1;

        queue.offer(now);
        boolean flag = false;
        int answer = 1;
        while (!queue.isEmpty()) {
            now = queue.poll();
            if (visited[now[0].x][now[0].y][now[1].x][now[1].y] >= 11){
                break;
            }

            for (int i = 0; i < mx.length; i++) {
                Pair temp1 = new Pair(now[0].x + mx[i], now[0].y + my[i]);
                Pair temp2 = new Pair(now[1].x + mx[i], now[1].y + my[i]);

                boolean check1 = (temp1.x < 0 || temp1.x >= n || temp1.y < 0 || temp1.y >= m) ? true : false;
                boolean check2 = (temp2.x < 0 || temp2.x >= n || temp2.y < 0 || temp2.y >= m) ? true : false;
                if (check1 && !check2) {
                    flag = true;
                    answer = visited[now[0].x][now[0].y][now[1].x][now[1].y];
                    break;
                }
                else if (!check1 && check2) {
                    flag = true;
                    answer = visited[now[0].x][now[0].y][now[1].x][now[1].y];
                    break;
                }
                else if (check1 && check2)
                    continue;

                if (board[temp1.x][temp1.y] == '#')
                    temp1 = now[0];
                if (board[temp2.x][temp2.y] == '#')
                    temp2 = now[0];

                if (visited[temp1.x][temp1.y][temp2.x][temp2.y] == 0) {
                    visited[temp1.x][temp1.y][temp2.x][temp2.y] = visited[now[0].x][now[0].y][now[1].x][now[1].y] + 1;
                    queue.offer(new Pair[]{temp1, temp2});
                }
            }
            if (flag)
                break;
        }
        if (flag) {
            System.out.println(answer);
        }
        else
            System.out.println(-1);
    }
    static class Pair {
        public int x;
        public int y;
        public Pair (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}