[백준]16197: 두 동전(java)

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

16197번: 두 동전

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1 

1 2
oo

예제 출력 1 

1

---

풀이

bfs문제였지만 동전을 동시에 2개 관리하는게 까다로운 문제였습니다.

동전 및 bfs에 사용할 클래스를 선언하였습니다.

static class Point{
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

동전은 map을 입력받을 때 

if(map[i][j] == 'o') {
    if(coin1 == null) {
        coin1 = new Point(i, j);
    } else {
        coin2 = new Point(i, j);
    }
}

위와 같은 조건으로 1, 2번 동전을 모두 입력 받습니다.

bfs를 시작하면 우리는 동전 두개가 동시에 같은 방향으로 움직인다는 것을 주의해야합니다.

평소와 같지만 visited 배열을 HashSet 자료구조로 coin1의 x좌표, y좌표 + coin2의 x좌표 y좌표를

문자열로 만들어서 방문했는지 확인해주었습니다.

String start = "";
start+=coin1.x;
start+=coin1.y;
start+=coin2.x;
start+=coin2.x;
start+=coin2.y;
visited.add(start);

코인 두개를 bfs로 쓰기위해서 Queue 자료구조를 다음과 같이 선언하였습니다.

Queue<Point[]> q = new LinkedList<>();

- 문제는 버튼을 10보다 많이 누를 시 종료된다.

if(depth > 10) return -1;

- 두개의 코인중 한개만 떨어졌을 때 우리는 버튼을 누른 횟수를 반환한다.

if((!isIn(nx1, ny1) && isIn(nx2, ny2)) || (isIn(nx1, ny1) && !isIn(nx2, ny2))) {
    return depth;
}

- 코인이 둘 다 떨어지면 안 된다.

if((!isIn(nx1, ny1) && !isIn(nx2, ny2))) continue;

- 코인이 둘 다 벽에 막히면 이동할 수 없다.

if(map[nx1][ny1] == '#' && map[nx2][ny2] == '#') continue;

- 코인1, 코인2중에 하나만 벽에 막혔다면

if(map[nx1][ny1] == '#' && map[nx2][ny2] != '#') {
    if(now[0].x == nx2 && now[0].y == ny2) continue;
    nx1 = now[0].x;
    ny1 = now[0].y;
} else if(map[nx1][ny1] != '#' && map[nx2][ny2] == '#') {
    if(now[1].x == nx1 && now[1].y == ny1) continue;
    nx2 = now[1].x;
    ny2 = now[1].y;
}

> 벽에 막힌 코인은 움직이지 않아야 하므로 원래의 위치로 세팅해준다.

> 이 때 벽에 막히지 않은 코인이 벽에 막힌 코인 자리로 갈 수 있음을 예외처리 해주었다.

- 이후에 이동한 코인의 위치가 이미 방문했던 자리라면 다시 갈 필요가 없다.

String next = "";
next+=nx1;
next+=ny1;
next+=nx2;
next+=ny2;

if(visited.contains(next)) continue;

- 위의 조건에 걸리지 않았다면

visited.add(v);
q.add(new Point[]{new Point(nx1, ny1), new Point(nx2, ny2)});

 

전체 코드

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

public class BJ_G4_16197_두동전 {
    static class Point{
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static char[][] map;
    static int N, M;
    public static void main(String[] args) throws Exception {
        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];
        Point coin1 = null;
        Point coin2 = null;
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j] == 'o') {
                    if(coin1 == null) {
                        coin1 = new Point(i, j);
                    } else {
                        coin2 = new Point(i, j);
                    }
                }
            }
        }
        System.out.printf("%d", bfs(coin1, coin2));
    }

    public static int bfs(Point coin1, Point coin2) {
        Queue<Point[]> q = new LinkedList<>();
        HashSet<String> visited = new HashSet<>();
        int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        q.add(new Point[] {coin1, coin2});
        String start = "";
        start+=coin1.x;
        start+=coin1.y;
        start+=coin2.x;
        start+=coin2.x;
        start+=coin2.y;
        visited.add(start);

        int depth = 1;

        while (!q.isEmpty()) {
            if(depth > 10) return -1;
            int len = q.size();
            for(int l=0; l<len; l++) {
                Point[] now = q.poll();

                for(int i=0; i<4; i++) {
                    int nx1 = now[0].x + dist[i][0];
                    int ny1 = now[0].y + dist[i][1];

                    int nx2 = now[1].x + dist[i][0];
                    int ny2 = now[1].y + dist[i][1];

                    if((!isIn(nx1, ny1) && isIn(nx2, ny2)) || (isIn(nx1, ny1) && !isIn(nx2, ny2))) {
                        return depth;
                    }
                    if((!isIn(nx1, ny1) && !isIn(nx2, ny2))) continue;

                    if(map[nx1][ny1] == '#' && map[nx2][ny2] == '#') continue;

                    if(map[nx1][ny1] == '#' && map[nx2][ny2] != '#') {
                        if(now[0].x == nx2 && now[0].y == ny2) continue;
                        nx1 = now[0].x;
                        ny1 = now[0].y;
                    } else if(map[nx1][ny1] != '#' && map[nx2][ny2] == '#') {
                        if(now[1].x == nx1 && now[1].y == ny1) continue;
                        nx2 = now[1].x;
                        ny2 = now[1].y;
                    }
                    String next = "";
                    next+=nx1;
                    next+=ny1;
                    next+=nx2;
                    next+=ny2;

                    if(visited.contains(next)) continue;

                    visited.add(next);
                    q.add(new Point[]{new Point(nx1, ny1), new Point(nx2, ny2)});
                }
            }
            depth++;
        }

        return -1;
    }

    public static boolean isIn(int x, int y) {
        return 0<=x && x<N && 0<=y && y<M;
    }
}