[BOJ 16197] 두 동전

#문제

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

#풀이

해당 문제는 BFS로 풀었습니다.

보통 저는 문제에서 "어디서부터 어디까지의 최단 거리를 구해라!" 라고 한다면 BFS 방식으로 문제를 풉니다.

DFS로 풀어도 괜찮습니다!  다른 블로그에서는 DFS로 풀이를 하셨더라구요. 

DFS로 풀다 모르시면 구글링하시면 될 것 같습니다. :)

눈 여겨 볼 조건은 "이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다." 와

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

조건들을 잘 보고 생각하며 코딩을 할 수 있도록 습관을 들입시다!

첫 번째로 두 동전이 어느 칸으로 움직였을때 버튼을 누른 수를 저장해야합니다.

두개의 동전이 한번에 움직이므로 두 동전의 위치를 한번에 저장할 수 있도록 구조체를 만들어 주었습니다.

(1번째 코인 : [r1, c1] , 2번째 코인 : [r2, c2])

그리고 떨어진 동전을 확인하기 위해 맵을 사방으로 한칸씩 늘려줍니다.

N과 M이 최대 20까지 될 수 있으므로 맵의 최대 너비와 높이는 22가 됩니다.

그 후, BFS을 통해 코인을 움직이며 코인들의 위치에서 누른 버튼의 값을 저장하며 진행합니다.

4차원 배열 -> dist[r1][c1][r2][c2] : 1번째 코인이 (c1, r1) 2번째 코인이 (c2,r2)일때의 누른 버튼의 수

다른 기본 BFS 문제들과 비슷하기 때문에 이해하기 편하실 것 같습니다.

#코드

#include <iostream>
#include <queue>
 
using namespace std;
 
struct Coin{
    int r1,c1,r2,c2;
};
 
int N,M;
char map[22][22];
int dist[22][22][22][22];
 
int dr[4] = {-1,1,0,0};
int dc[4] = {0,0,-1,1};
 
bool isOut(int r, int c){
    if(r < 1 || r > N || c < 1 || c > M) return true;
    return false;
}
 
void dropTheOneBall(Coin coin){
    queue<Coin> q;
    q.push(coin);
    while(!q.empty()){
        Coin c = q.front();
        q.pop();
        int r1 = c.r1 , c1 = c.c1, r2 = c.r2, c2 = c.c2;
        //10번 이상 버튼을 눌렀을때 두 구슬 모두 떨어지지 않았다면 -1출력
        if(dist[r1][c1][r2][c2] > 10) break;
        //두개 코인중 하나만 떨어졌을때
        if(isOut(r1, c1) ^ isOut(r2, c2)){
            cout << dist[r1][c1][r2][c2] << endl;
            return;
        }
        for(int i = 0; i < 4; i++){
            int nr1 = r1 + dr[i], nc1 = c1 + dc[i];
            int nr2 = r2 + dr[i], nc2 = c2 + dc[i];
            
            //방문했는지 체크
            if(dist[nr1][nc1][nr2][nc2] > 0) continue;
            
            //두개 코인 모두 떨어졌을때
            if(isOut(nr1, nc1) && isOut(nr2, nc2)) continue;
            
            //두개 코인 모두 벽에 부딪혔을때
            if(map[nr1][nc1] == '#' && map[nr2][nc2] == '#') continue;
            //두 코인 중 하나만 벽에 부딪혔을때
            if(map[nr1][nc1] == '#'){
                nr1 = r1;
                nc1 = c1;
            }else if(map[nr2][nc2] == '#'){
                nr2 = r2;
                nc2 = c2;
            }
            
            Coin nextCoin;
            nextCoin.r1 = nr1;
            nextCoin.c1 = nc1;
            nextCoin.r2 = nr2;
            nextCoin.c2 = nc2;
            q.push(nextCoin);
            //거리 늘려주기
            dist[nr1][nc1][nr2][nc2] = dist[r1][c1][r2][c2] + 1;
        }
    }
    //끝날때 까지 못 나갔을 경우
    cout << -1 << endl;
}
 
int main(){
    cin >> N >> M;
    int ballCnt = 1;
    Coin coin;
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= M; j++){
            cin >> map[i][j];
            if(map[i][j] == 'o'){
                if(ballCnt == 1){
                    coin.r1 = i;
                    coin.c1 = j;
                    ballCnt++;
                }else{
                    coin.r2 = i;
                    coin.c2 = j;
                }
            }
        }
    }
    dropTheOneBall(coin);
    return 0;
}