[백준]16197: 두 동전 - JAVA

[백준]16197: 두 동전

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

16197번: 두 동전

풀이

조건에 맞게 동전들을 이동하다가 하나의 동전만 떨어뜨릴 수 있는 최소값을 찾는 문제이므로 BFS탐색을 활용하였다.

 

보드를 입력 받을 때 동전의 위치는 Coin객체를 생성하여 따로 저장해 주었다.

방문체크는 boolean배열을 4차원으로 선언하였다. 두 개의 동전이 한번에 움직이므로 동시에 체크해줄 필요가 있어 4차원으로 선언하여 사용한다.

 

그럼 이제 BFS함수를 어떻게 구현해야 할지 순서대로 생각해보자.

1. 현재 코인들의 위치 정보와 버튼을 누른횟수가 필요하므로 두 동전의 현재 위치와 현재 버튼을 누른 횟수를 저장하는 towCoins 객체를 생성하여 사용한다.
2. 현재 버튼을 누른 횟수가 10 이상이라면 조건에 부합하지 않는 결과이므로 반복문을 빠져나와 "-1"을 출력한다.
3. 현재 동전들의 위치에서 위, 아래, 왼, 오른쪽 4방향 탐색을 시작한다. 두 동전 모두 한번에 진행한다.
4. 만약 두 개의 동전이 이동할 좌표가 벽이라면, 이동할 수 없으므로 제자리로 돌아오도록 한다.
5. 떨어지지 않는 동전의 개수를 세어 주기 위해 동전 하나씩 이동할 위치가 유효한 범위 내에 있는지 확인한다.
6. 떨어지지 않는 동전의 개수가 하나라면, 찾는 정답이므로 count+1을 return한다.
7. 떨어지지 않는 동전의 개수가 두개면서 방문한 적 없는 곳이라면 해당 좌표로 이동하고 탐색을 계속 진행한다.

 

풀고보니 쉽게 느껴지는데 조건 처리하고 코드를 더 이뿌게 다듬느라 1시간30분정도 걸린 것 같다. 처음에 조건 확인을 제대로 안했다 디버깅 하는데 너무 많은 시간을 소비했다..ㅎㅎ

 

이정도 문제는 코테에서 자주 볼 수 있는 난이도와 유형이라는 생각이 든다!

 

코드

import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static char[][] board;
    static Coin[] coin; // 동전의 위치 저장. 
    static boolean[][][][] visited;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
 
        board = new char[n][m];
        coin = new Coin[2];
        int coinIdx = 0;
        for(int i = 0; i < n; i++) {
            String str = scan.next();
            for(int j = 0; j < m; j++) {
                char c = str.charAt(j);
                if(c == 'o') {
                    coin[coinIdx++] = new Coin(i, j); //코인의 위치 저장 
                }
                board[i][j] = c;
            }
        }
 
        visited = new boolean[n][m][n][m]; //[첫번째동전의x위치][첫번째동전의y위치][두번째동전의x위치][두번째동전의y위치]
        System.out.println(bfs());
    }
 
    public static int bfs() {
        Queue<towCoins> q = new LinkedList<>();
        q.offer(new towCoins(coin[0].x, coin[0].y, coin[1].x, coin[1].y, 0));
        visited[coin[0].x][coin[0].y][coin[1].x][coin[1].y] = true;
 
        while(!q.isEmpty()) {
            towCoins current = q.poll();
 
            if(current.count >= 10) break;
 
            for(int i = 0; i < 4; i++) {
                int nx1 = current.x1 + dx[i];
                int ny1 = current.y1 + dy[i];
                int nx2 = current.x2 + dx[i];
                int ny2 = current.y2 + dy[i];
                
                //이동할 좌표가 벽이면 이동할 수 없으므로 이동하지 않는다.
                if(!canMoveCoin(nx1, ny1)) { 
                    nx1 = current.x1;
                    ny1 = current.y1;
                }
                if(!canMoveCoin(nx2, ny2)) {
                    nx2 = current.x2;
                    ny2 = current.y2;
                }
 
                int flag = 0; //떨어지지 않는 동전의 개수
                if(nx1 >= 0 && ny1 >= 0 && nx1 < n && ny1 < m) flag++;
                if(nx2 >= 0 && ny2 >= 0 && nx2 < n && ny2 < m) flag++;
 
                if(flag == 1) return current.count + 1;
                else if(flag == 2 && !visited[nx1][ny1][nx2][ny2]) {
                    visited[nx1][ny1][nx2][ny2] = true;
                    q.offer(new towCoins(nx1, ny1, nx2, ny2, current.count + 1));
                }
            }
        }
        return -1;
    }
 
    public static boolean canMoveCoin(int nx, int ny) {
        if(nx >= 0 && ny >= 0 && nx < n && ny < m && board[nx][ny] == '#') {
            return false;
        }
        return true;
    }
 
    public static class towCoins { //두 동전의 위치와 현재 버튼을 누른 횟수를 기록하는 객체
        int x1;
        int y1;
        int x2; 
        int y2;
        int count;
 
        public towCoins(int x1, int y1, int x2, int y2, int count) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
            this.count = count;
        }
    }
 
    public static class Coin { //동전의 좌표를 기억하는 객체
        int x;
        int y;
 
        public Coin(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}