[BOJ] 두 동전

문제

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

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

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

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

입력

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

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

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

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

 

풀이

16197

맞았습니다!!

23872

40

C++14 / 수정

3245

1분 전

 

1. 시뮬레이션

 

2. 두 동전의 좌표를 모두 한 큐에 넣어서 같은 방향으로 이동시킨다. 

총 네가지 경우가 있다. 

• 동전1이 영역 밖에 있을 때 동전 2는 영역 안에 있는 경우 
• 동전 1이 영역 밖에 있을 때 동전 2도 영역 밖에 있는 경우 
• 동전 1이 영역 안에 있을 때 동전 2는 영역 밖에 있는 경우 
• 동전 1,2가 모두 영역 안에 있는 경우 

3. 1번, 3번의 경우에는 버튼을 누른 횟수를 return 한다. 

2번의 경우에는 continue로 다음 방향으로 이동하도록 한다. 

4번의 경우에는 이제 벽인지 아닌지 판단해서 벽인 경우에는 원래 좌표를, 벽이 아닌 경우에는 움직인 좌표를 큐에 넣어준다. 

 

4. bfs를 돌린 결과 ans가 여전히 최대값(11)라면 동전이 밖에 덜어질 일이 없거나 버튼을 10번 넘게 누른 경우이기 때문에 -1을 출력한다. 

 

---

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int n, m;
char map[21][21];
int ans = 11;
int dx[4] = {0,0,-1,1}, dy[4] = {-1,1,0,0};
bool visited[21][21][21][21];
 
typedef pair<int, int> pp;
typedef pair<pp, pp> pppp;
typedef pair<pppp, int> ppppp;
 
int coin[2][2];
 
void bfs() {
    queue<ppppp> q;
    q.push(ppppp(pppp(pp(coin[0][0], coin[0][1]), pp(coin[1][0], coin[1][1])), 0));
    visited[coin[0][0]][coin[0][1]][coin[1][0]][coin[1][1]] = true;
 
    int cnt = 0;
    while(!q.empty()) {
 
       
 
        int x1 = q.front().first.first.first;
        int y1 = q.front().first.first.second;
        int x2 = q.front().first.second.first;
        int y2 = q.front().first.second.second;
        int step = q.front().second;
 
         if (step == 10) break;
 
        q.pop();
 
        bool flag = false;
        for (int i = 0; i < 4; i++) {
            int nx1 = x1 + dx[i];
            int ny1 = y1 + dy[i];
            int nx2 = x2 + dx[i];
            int ny2 = y2 + dy[i];
            
            if (!(nx1 >= 0 && nx1 < n && ny1 >= 0 && ny1 < m )) {
                if (nx2 >= 0 && nx2 < n && ny2 >= 0 && ny2 < m) {
                    ans = min(ans, step+1);
                    return;
                }
                else continue; //둘 다 경계밖
            }
            else { //동전1은 경계 안에 있음
                if (!(nx2 >= 0 && nx2 < n && ny2 >= 0 && ny2 < m)) {
                    ans = min(ans, step+1);
                    return;
                }
                else flag = true;
            }
 
            if (map[nx1][ny1] == '#'){
                if (map[nx2][ny2] != '#') {
                    q.push(ppppp(pppp(pp(x1, y1), pp(nx2, ny2)), step+1));
                    visited[x1][y1][nx2][ny2] = true;
                }
                else {
                    q.push(ppppp(pppp(pp(x1, y1), pp(x2, y2)), step+1));
                     visited[x1][y1][x2][y2] = true;
                }
            }
            else {
               if (map[nx2][ny2] == '#') {
                   q.push(ppppp(pppp(pp(nx1, ny1), pp(x2, y2)), step+1));
                    visited[nx1][ny1][x2][y2] = true;
               }
               else {
                   q.push(ppppp(pppp(pp(nx1, ny1), pp(nx2, ny2)), step+1));
                    visited[nx1][ny1][nx2][ny2] = true;
               }
            }
        }
    
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
 
    bool flag = false;
    for (int i = 0;i< n; i++) {
        string tmp;
        cin>>tmp;
        for (int j = 0; j < m; j++) {
            map[i][j] = tmp[j];
            if (map[i][j] == 'o') {
                if (!flag)  {
                    coin[0][0] = i;
                    coin[0][1] = j;
                    flag = true;
                }
                else{
                    coin[1][0]= i;
                    coin[1][1]= j; 
                }
            }
        }
    }//input 
 
    //두 동전은  동시에 이동 (같은 방향으로 )
 
    bfs();
 
    if (ans == 11) cout << -1 << '\n';
    else cout << ans << '\n';
 
    return 0;
}