두 동전

📍 문제 설명

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

16197번: 두 동전

 

💡 접근

구슬 탈출이랑 비슷한 문제였는데, 버튼을 10번 이상이 아니라 10번 보다 많이 누르면 -1를 출력해야한다....

각 동전은 동시에 움직이지만 한 동전이 움직일 수 없는 경우 제자리에 있고 다른 동전은 움직일 수 있으면 움직여야한다.

 

 

👩‍💻 코드

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

public class Main {
    static int s, n, m , v, e, k, r, x = 21, y = 21, answer, cnt, add, sub, mul, div, max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    static int[] arr, dice;
    static long[] dp;
    static char[][] board;
    static boolean[][][][] visited;
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    static ArrayList<Integer> list;
    static StringBuilder sb;
    static Queue<Point> q;
    public static void main(String[] args) throws IOException {
        Main T = new Main();
        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];
        q = new LinkedList<>();

        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                board[i][j] = str.charAt(j);
                if(board[i][j] == 'o' && x != 21 && y != 21) {
                    q.offer(new Point(x, y, i, j));
                    visited[x][y][i][j] = true;
                }
                if(board[i][j] == 'o') {
                    x = i;
                    y = j;
                }
            }
        }

        T.solution();
    }

    private void solution() {
        cnt = 1;
        while(!q.isEmpty()) {
            int len = q.size();
            for (int c = 0; c < len; c++) {
                if (cnt > 10) {
                    System.out.println(-1);
                    System.exit(0);
                }
                Point cp = q.poll();
                for (int i = 0; i < 4; i++) {
                    int nx1 = cp.x1 + dx[i];
                    int ny1 = cp.y1 + dy[i];
                    int nx2 = cp.x2 + dx[i];
                    int ny2 = cp.y2 + dy[i];

                    //동전이 둘 다 떨어지는 경우 n = 1 m = 2 1,0 1,1
                    if ((nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= m) && (nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= m)) continue;
                    //동전이 둘 중 하나 떨어지는 경우
                    else if ((nx1 < 0 || nx1 >= n || ny1 < 0 || ny1 >= m) || (nx2 < 0 || nx2 >= n || ny2 < 0 || ny2 >= m)) {
                        System.out.println(cnt);
                        System.exit(0);
                    }
                    //벽이면 해당 동전은 움직일 수 없다.
                    if (board[nx1][ny1] == '#') {
                        nx1 = cp.x1;
                        ny1 = cp.y1;
                    }
                    if (board[nx2][ny2] == '#') {
                        nx2 = cp.x2;
                        ny2 = cp.y2;
                    }

                    if (!visited[nx1][ny1][nx2][ny2]) {
                        visited[nx1][ny1][nx2][ny2] = true;
                        q.offer(new Point(nx1, ny1, nx2, ny2));
                    }
                }
            }
            cnt++;
        }
        System.out.println(-1);
    }

    private static class Point {
        private int x1;
        private int y1;
        private int x2;
        private int y2;

        public Point(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x1=" + x1 +
                    ", y1=" + y1 +
                    ", x2=" + x2 +
                    ", y2=" + y2 +
                    '}';
        }
    }
}