[BOJ]두 동전(16197)

www.acmicpc.net/problem/16197

16197번: 두 동전

분류 - BFS

난이도- 골드4

 

문제

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

풀이

 아주 단순한 BFS 미로찾기 문제이다. 필자의 경우 보드의 크기를 상,하,좌,우 모두 1씩 더 크게하여(N+2, M+2) 움직이지 못하는 경우와 똑같이 처리하여 범위 조건을 생략한다.

 처음에는 4차 배열을 이용하여 check(visited) 처리를 했지만 다른 코드를 보고 문자열 Set으로 대체했다.(속도가 훨씬 빨라졌다;;)(264ms --> 156ms)

 

1.  입력을 받으며 두 동전의 위치를 coins에 저장한다.

2. 현재 두 동전의 위치를 check에 표시한후(set을 이용하여 coin1-coin2, coin2-coin1순서 모두 체크) queue에 status상태로 push한다.

3. queue에서 하나씩 dequeue(shift()) 하며 check를 하고(check에 이미 해당 위치가 있으면 스킵) 다음 위치에 대해서 판단하여 둘 중 하나만 떨어지면 res변수에 현재 count를 저장하고 break를 한다.

4. 둘 중 한 동전만 움직이지 않거나 모두 다음 칸으로 이동하면 queue에 넣는다.

5. count가 10보다 크면 더이상 enqueue하지 않는다.

6. BFS while문은 res의 초기값이 -1이고 res가 0보다 크거나 queue에 원소가 없으면 종료한다.

7. count가 10보다 크면 더이상 enqueue하지 않는다.

 

코드

const input = require("fs").readFileSync("./dev/stdin").toString().trim().split("\n");

const temp =input[0].trim().split(' ').map(function(a){return parseInt(a)});
const N=temp[0],M= temp[1];
input.shift();  // 첫번째 줄 제거
var board = Array.from({length:N+2}, (i)=>Array.from({length:M+2}, (_,i)=>' '));
var map = new Map();
class Coin{			// 코인의 좌표
    constructor(y,x){
        this.y = y;
        this.x = x;
    }
}
class State{		// 2개의 코인과 이동 횟수
    constructor(coins, count){
        this.coins = coins;	// [coins1, coins2]
        this.count = count;
    }
}
var coins = [];
input.forEach(function(str, i){
    var line = i+1;
    var curStr = str.trim();
    for(var i =0 ; i< M; i++){
        board[line][i+1] = str[i];
        if(str[i]=='o') coins.push(new Coin(line,i+1));		// 동전일 경우
    }
});

var check = new Set();
check.add(coins[0].y+'-'+coins[0].x+'-'+coins[1].y+'-'+coins[1].x);
check.add(coins[1].y+'-'+coins[1].x+'-'+coins[0].y+'-'+coins[0].x);
		// y1-x1-y2-x2 형식으로 저장된다.
        // 두 동전의 위치가 서로 바뀌어도 똑같기 때문에 
        // y1-x1-y2-x2 과 y2-x2-y1-x1 모두 set에 저장해 준다.
        
var queue = [];			// JS에서 큐는 push()-enqueue, shift()-dequeue로 간단히 구현된다.
queue.push(new State(coins, 0));
var dy = [0,0,1,-1];
var dx = [1,-1,0,0];
var res =-1;
while(queue.length>0){
    var cur = queue.shift();
    var coin1 = cur.coins[0];
    var coin2 = cur.coins[1];
    var count = cur.count;
    count++;
    if(count>10) continue;
    for(var i =0; i< 4; i++){
        var ny1 = coin1.y+dy[i];
        var nx1 = coin1.x+dx[i];
        var ny2 = coin2.y+dy[i];
        var nx2 = coin2.x+dx[i];
        if(check.has(ny1+'-'+nx1+'-'+ny2+'-'+nx2)) continue; // 이전에 들른 곳
        check.add(ny1+'-'+nx1+'-'+ny2+'-'+nx2);
        check.add(ny2+'-'+nx2+'-'+ny1+'-'+nx1);		// 떨어지거나 갈 수 없어도 체크해 준다.
        													// 아래 로직을 수행 하지 않는게 더 빠르기 때문
        if(board[ny1][nx1]==' ' && board[ny2][nx2]==' '){   // 둘다 떨어지면 안됨
            continue;
        }else if(board[ny1][nx1]==' ' || board[ny2][nx2]==' '){  // 둘 중 하나만 떨어지면 끝
            res = count;									// if에서 둘다 떨어지는 것을 걸렀기 때문에
            break;											// OR 조건으로 가능하다
        }
        if(board[ny1][nx1]=='#' && board[ny2][nx2]=='#') continue;  // 움직이지 못하므로 생략
        if(board[ny1][nx1]=='#'){   // 다음 목표가 벽이면 움직이지 않음
            ny1=coin1.y;
            nx1=coin1.x;
        }
        if(board[ny2][nx2]=='#'){   // 다음 목표가 벽이면 움직이지 않음
            ny2=coin2.y;
            nx2=coin2.x;
        }
        if(ny1==ny2 && nx1==nx2) continue;			// 겹치면 하나만 떨어질 수 없기에 생략
        queue.push(new State([new Coin(ny1,nx1),new Coin(ny2,nx2)], count));
    }
    if(res>0) break;
}

console.log(res);