[BOJ]두 동전(16197)

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력 1 복사

1 2 oo

예제 출력 1 복사

1

예제 입력 2 복사

6 2 .# .# .# o# o# ##

예제 출력 2 복사

4

예제 입력 3 복사

6 2 .. .. .. o# o# ##

예제 출력 3 복사

3

예제 입력 4 복사

5 3 ### .o. ### .o. ###

예제 출력 4 복사

-1

예제 입력 5 복사

5 3 ### .o. #.# .o. ###

예제 출력 5 복사

3

풀이

1. 먼저 board에 보드 내용을 받는다.

2. queue에 넣어서 board상황을 bfs에 넣어 사용하기 위해, Pair과 Condition을 만들었다.

3. 상황에 맞게 다음 위치가 '\u0000'일 경우 동전이 떨어지는 경우로 자바 char 형의 기본값인다. 이 경우 fall을 하나증가시킨다.

4. fall이 1개면 cnt를 출력하고 종료한다.

5. 만약 fall이 2개면 동전이 두개 다 빠진 것으로 건너 뛴다.

6. 그런 경우를 제외하면 fall이 0인 상황인데 이를 재활용하여(다시 변수를 만들기엔 귀찮기...) '#'일 경우 우선 dx[d], dy[d]를 감소시켜 움직임을 취소하고 fall을 하나 증가시키고 다시 fall이 2개일 경우는 불가능한 상태이므로 continue, fall이 1개이면 p1과 p2가 같을 경우는 불가능한 경우이므로 continue한다.

7. 이 모든 상황이 아닐 경우에는 둘다 '.' 혹은 움직이지 않은 경우이므로 queue에 넣어서 bfs를 진행한다.

※배운(느낀)점

처음에는 Pair p1 = now.p1; Pair p2 = now.p2 로 했다. 이렇게 했을 때 p1, p2가 now.p1, now.p2의 주소를 가리켜 now 자체가 바뀌게 되므로 새로 인스턴스를 생성해 준 후 p1, p2를 다뤄야 한다.

기본적인 사실이지만 실제로 사용할 때는 자칫 잊을 수 있으니 주의해야 할 것같다.

-관련내용(5. Value vs Reference 부분)

https://develaniper-devpage.tistory.com/97?category=484188 

[프로그래밍언어] 자바(1) 비 언어적 부분( 구성, 특성 )

코드

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


class Pair{
    int x,y;
    Pair(int y, int x){
        this.x=x;this.y=y;
    }
    Pair(Pair p){
        this.x = p.x;
        this.y = p.y;
    }
    @Override
    public boolean equals(Object obj) {
        Pair p2 = (Pair)obj;
        if(this.x!=p2.x) return false;
        if(this.y!=p2.y) return false;

        return true;
    }
}
class Condition{
    Pair p1=null,p2=null;
    int count;
    Condition(){}
    Condition(Pair p1, Pair p2, int count){
        this.p1 = p1; this.p2=p2;
        this.count = count;
    }
    void pushP(Pair p){
        if(p1==null){
            this.p1=p;
        }else{
            this.p2=p;
        }
    }
}
class BOJ16175{

    public static void checkVisit(Pair p1, Pair p2, boolean[][][][] visit){
        visit[p1.y][p1.x][p2.y][p2.x]=true;
        visit[p2.y][p2.x][p1.y][p1.x]=true;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        char[][] board = new char[N+2][M+2];
        boolean[][][][] visit = new boolean [N+2][M+2][N+2][M+2];

        Condition c = new Condition();
        for(int i =1; i<= N; i++){
            String str = br.readLine();
            for(int j=1; j<=M; j++){
                board[i][j]= str.charAt(j-1);
                if(board[i][j]=='o'){
                    c.pushP(new Pair(i, j));
                }
            }
        }

        Queue<Condition> q = new LinkedList<>();
        q.add(c);
        checkVisit(c.p1, c.p2, visit);
        int[] dy = {0 ,1,0,-1};
        int[] dx = {1,0,-1, 0};
        int result =-1;
        while(!q.isEmpty()){
            Condition now = q.poll();
            int cnt = now.count+1;
            if(cnt>10 || result>0){
                break;
            }
            for(int d = 0; d<4; d++){
                Pair p1 = new Pair(now.p1);
                Pair p2 = new Pair(now.p2);
                int fall = 0;
                p1.y += dy[d];p1.x += dx[d];
                p2.y += dy[d];p2.x += dx[d];
                if(board[p1.y][p1.x]=='\u0000'){
                    fall++;
                }
                if(board[p2.y][p2.x]=='\u0000'){
                    fall++;
                }
                if(fall==1){
                    result = cnt;
                    break;
                }
                else if(fall==2){
                    continue;
                }
                if(board[p1.y][p1.x]=='#'){
                    p1.y -= dy[d];
                    p1.x -= dx[d];
                    fall++;
                }
                if(board[p2.y][p2.x]=='#'){
                    p2.y -= dy[d];
                    p2.x -= dx[d];
                    fall++;
                }
                if(fall==2 || p1.equals(p2)){
                    continue;
                }
                if(!visit[p1.y][p1.x][p2.y][p2.x]){
                    q.add(new Condition(p1, p2, cnt));
                }
            }
        }
        System.out.println(result);
    }
}