[백준 *Java] - 두 동전(16197)

두 동전

16197번: 두 동전

 

문제

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

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

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

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

입력

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

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

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

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

출력

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

---

👇 접근방식

하.. 백준 문제들 진짜 몇 번씩 읽어야하는 거야.. 진짜......
처음에 문제가 이해되지 않았고, 테케를 보는데도 이해가 안됐습니다..
그러다가 그냥 머리 속으로 생각나는대로 구현을 시도해보는데, 의문점이 하나가 생겨, 순간적으로 문제를 이해가 됐던 거 같네요.
두 동전이 한 턴 기회에 동시에 상하좌우로 움직이되,
만약 둘 다 out 되면 안되고, 무조건 동전 하나만 out 되는 상황에서 프로그램 종료
또는 최대 10번 이상 많이 움직이게 된다면, 종료 해야합니다.
이렇게 문제를 보고 다시 생각정리를 하니, 문제가 이해되고, 테케가 이해되기 시작했습니다.

일단 로직 설계는 
1. 두 동전의 좌표값을 알고 있어야한다.
2. 보드에 입력값을 저장해놓고 그걸 이용한다.
3. BFS를 사용해서, 4방면을 이동 할 시, map에서 동전이 몇 개가 떨어지는지? 두 동전이 벽을 만났는 지?
큰 flor을 이렇게 생각했습니다

BFS 조건 정리는
순서대로
0. 이동 횟수가 10회이상인지?
1. 동전 둘 다 아웃됐을 시? 
2. 하나만 아웃됐을 시?
3. 벽을 만났는 지? 안 만났는 지?
로 조건을 잡았습니다.

 

아래는 성공한 코드입니다.

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

public class Main {
    static int N, M; // 세로, 가로
    static char[][] map;
    static Queue<Node> qu;
    static int[] dx = {-1, 0, 1, 0}; // 시계방향으로 북동남서
    static int[] dy = {0, 1, 0, -1};
    static final int fourDirection = 4;

    static class Node {
        int x;
        int y;
        int moveCnt;

        public Node(int x, int y, int moveCnt) {
            this.x = x;
            this.y = y;
            this.moveCnt = moveCnt;
        }
    }

    static int rangeCheck(int x1, int y1, int x2, int y2) {
        int chk = 0;
        if (x1 < 0 || x1 >= N || y1 < 0 || y1 >= M) chk += 1;
        if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= M) chk += 1;
        return chk;
    }

    static void addCoinPoint(int nx, int ny, Node curCoin) {
        if (map[nx][ny] == '#')
            qu.offer(new Node(curCoin.x, curCoin.y, curCoin.moveCnt + 1));
        else
            qu.offer(new Node(nx, ny, curCoin.moveCnt + 1));
    }

    static int bfs() {
        while (!qu.isEmpty()) {
            Node coin1 = qu.poll();
            Node coin2 = qu.poll();

            if (coin1.moveCnt >= 10) return -1;
            for (int i = 0; i < fourDirection; i++) {
                int nCoin1_x = coin1.x + dx[i];
                int nCoin1_y = coin1.y + dy[i];
                int nCoin2_x = coin2.x + dx[i];
                int nCoin2_y = coin2.y + dy[i];

                // 둘 다 아웃 했을 시?
                int chkNum = rangeCheck(nCoin1_x, nCoin1_y, nCoin2_x, nCoin2_y);
                if (chkNum == 2) continue;
                if (chkNum == 1) return coin1.moveCnt + 1;

                addCoinPoint(nCoin1_x, nCoin1_y, coin1);
                addCoinPoint(nCoin2_x, nCoin2_y, coin2);
            }
        }
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 세로
        M = Integer.parseInt(st.nextToken()); // 가로

        map = new char[N][M];
        qu = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < line.length; j++) {
                map[i][j] = line[j];
                if (line[j] == 'o') {
                    qu.offer(new Node(i, j, 0)); // 동전 위치값 삽입
                }
            }
        }
        int result = bfs();
        System.out.println(result == -1 ? -1 : result);
    }
}