백준 - 16197 두 동전(Java)

bfs 문제입니다.

 

보드의 크기는 N*M입니다.

보드 위에 두 개의 동전, 빈칸, 벽(이동 불가능한 위치) 가 주어집니다.

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

버튼을 누르면 두 개의 동전이 동시에 네 방향(상, 하, 좌, 우) 중 한 방향으로 움직일 때,

단 한 개의 동전만 떨어뜨리는 최소 경우의 수를 구하는 문제입니다.

 

문제 접근 순서는 다음과 같습니다.

1. 동전이 하나만 떨어져 있는지 확인한다.(최소 갱신)
2. 동전을 네 방향으로 움직인다. (벽이 있는지 확인해야 한다.)
3. 동전을 움직였을 때, 두 개의 동전 상태를 구한다.
4. 1번을 반복한다.

※ 주의 사항

최소 버튼을 누르는 경우의 수가 10 초과일 경우 -1을 반환해야 합니다.

저는 10 이상으로 했었어서 오늘도 삽질을 했습니다....

또한, 문제를 잘못 읽어서 두 개의 동전을 모두 떨어뜨리도록 구현했었습니다 ㅠㅠ.

 

[구현 코드]

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    // 상, 하, 좌, 우
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};

    private static int n, m;
    private static char[][] map;

    private static class Coins {
        int x1, y1, x2, y2, cnt;
        boolean state1, state2;

        public Coins(int x1, int y1, int x2, int y2, int cnt, boolean state1, boolean state2) {
            this.x1 = x1; // 첫 번째 동전 x좌표
            this.y1 = y1; // 첫 번째 동전 y좌표
            this.x2 = x2; // 두 번째 동전 x좌표
            this.y2 = y2; // 두 번째 동전 y좌표

            this.cnt = cnt; // 버튼 누른 개수

            this.state1 = state1; // 첫 번째 동전 상태(true : 보드 내부, false : 보드 밖)
            this.state2 = state2; // 두 번째 동전 상태(true : 보드 내부, false : 보드 밖)
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");
        int answer = 0;

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());

        map = new char[n][m];

        Coins coins = null;
        int cnt = 0;
        int x1 = 0, y1 = 0;
        for (int i = 0; i < n; i++) {
            char[] tmp = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                if (tmp[j] != 'o') {
                    map[i][j] = tmp[j];
                } else {
                    if (cnt == 0) { // 첫 번째 동전의 좌표를 기억해둠
                        x1 = i;
                        y1 = j;
                        cnt++;
                    } else {
                        // 두 번째 동전이 나오면 첫 번재 동전의 정보와 함께 클래스로 저장함
                        coins = new Coins(x1, y1, i, j, 0, true, true);
                    }
                }
            }
        }

        // 버튼 개수를 구함
        answer = bfs(coins);

        answer = answer == Integer.MAX_VALUE ? (-1) : answer;

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }

    private static int bfs(Coins coins) {
        Queue<Coins> qu = new LinkedList<>();
        qu.add(coins);

        int cnt = Integer.MAX_VALUE;

        while (!qu.isEmpty()) {
            Coins cn = qu.poll();

            if (cn.cnt > 10) continue;

            // 둘 중 하나라도 밖으로 나갈 경우
            if (!cn.state1 || !cn.state2) {
                // 둘 다 밖으로 나갈 경우 제외 (실제로는 만들어 지지 않음)
                if (!cn.state1 && !cn.state2) {
                    continue;
                }
                // 둘 중 하나만 밖으로 나갈 경우의 최소를 저장함
                cnt = Math.min(cnt, cn.cnt);
                continue;
            }

            // 상, 하, 좌, 우
            for (int i = 0; i < 4; i++) {
                // 첫 번째 동전의 다음 위치
                int c1nx = cn.x1 + dx[i];
                int c1ny = cn.y1 + dy[i];

                // 두 번째 동전의 다음 위치
                int c2nx = cn.x2 + dx[i];
                int c2ny = cn.y2 + dy[i];

                // 두 개의 동전이 움직였을 때 밖으로 나갔는지, 안에 있는지 확임함
                boolean nc1 = inRange(c1nx, c1ny);
                boolean nc2 = inRange(c2nx, c2ny);

                // 다음 움직임이 둘 다 안에 있을 경우
                if (nc1 && nc2) {
                    // 둘 다 벽이 아닐 경우
                    if (map[c1nx][c1ny] != '#' && map[c2nx][c2ny] != '#') {
                        qu.add(new Coins(c1nx, c1ny, c2nx, c2ny, cn.cnt + 1, true, true));
                    }
                    // 첫 번째 동전 다음 움직임이 벽일 경우
                    else if (map[c1nx][c1ny] == '#' && map[c2nx][c2ny] != '#') {
                        qu.add(new Coins(cn.x1, cn.y1, c2nx, c2ny, cn.cnt + 1, true, true));
                    }

                    // 두 번째 동전 다음 움직임이 벽일 경우
                    else if (map[c1nx][c1ny] != '#' && map[c2nx][c2ny] == '#') {
                        qu.add(new Coins(c1nx, c1ny, cn.x2, cn.y2, cn.cnt + 1, true, true));
                    }
                }

                // 첫 번째 동전만 떨어질 경우
                else if (!nc1 && nc2) {
                    // 두 번째 동전 다음 움직임이 벽일 경우(두 번째 동전을 움직이지 않음)
                    if (map[c2nx][c2ny] == '#') {
                        qu.add(new Coins(c1nx, c1ny, cn.x2, cn.y2, cn.cnt + 1, false, true));
                    }
                    // 두 번째 동전 다음이 벽이 아닐 경우(두 번째 동전을 움직임)
                    else if (map[c2nx][c2ny] != '#') {
                        qu.add(new Coins(c1nx, c1ny, c2nx, c2ny, cn.cnt + 1, false, true));
                    }
                }

                // 두 번째 동전만 떨어질 경우
                else if (nc1 && !nc2) {
                    // 첫 번째 동전 다음 움직임이 벽일 경우(첫 번째 동전을 움직이지 않음)
                    if (map[c1nx][c1ny] == '#') {
                        qu.add(new Coins(cn.x1, cn.y1, c2nx, c2ny, cn.cnt + 1, true, false));
                    }
                    // 첫 번째 동전 다음이 벽이 아닐경우(첫 번째 동전을 움직임)
                    else if (map[c1nx][c1ny] != '#') {
                        qu.add(new Coins(c1nx, c1ny, c2nx, c2ny, cn.cnt + 1, true, false));

                    }
                }
            }
        }
        return cnt;
    }

    private static boolean inRange(int x, int y) {
        return x >= 0 && y >= 0 && x < n && y < m;
    }
}