[백준] 16197번 두 동전

문제 링크: https://www.acmicpc.net/problem/16197

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

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

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

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

입력

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

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

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

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

출력

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

문제 이해

두 동전을 동시에 움직여서 하나만 떨어뜨리는 문제이다.
두개의 동전을 움직일 때는 크게 세가지 작게는 여섯가지 문제가 존재한다.
1 - 둘다 떨어질 경우

• queue에 안 넣고 패스

2 - 둘다 안 떨어짐

• 한쪽이 벽인 경우 X 2 (둘다 queue에 넣는다.)
• 둘다 벽인 경우 패스

3 - 하나만 떨어지는 경우

• 결과 출력

코드 구현(c++)

#include <iostream>
#include <queue>

using namespace std;

typedef struct Node{
    int x;
    int y;
    int num;
}node;
queue<pair<node,node> > q;

int xCheck[4] = {-1,0,0,1};
int yCheck[4] = {0,-1,1,0};

int map[21][21];
int X,Y; 

int BFS(){
    while(!q.empty()){
        node tempNode1, tempNode2;
        node newNode1, newNode2;
        tempNode1 = q.front().first; tempNode2 = q.front().second;
        q.pop();
        if(tempNode1.num >= 10) break;
        for(int i = 0 ; i < 4 ; i++){
            int nX1 = tempNode1.x + xCheck[i]; int nX2 = tempNode2.x + xCheck[i];
            int nY1 = tempNode1.y + yCheck[i]; int nY2 = tempNode2.y + yCheck[i];
            if((nY1 < 0 || nX1 < 0 || nY1 >= Y || nX1 >= X) && (nY2 < 0 || nX2 < 0 || nY2 >= Y || nX2 >= X)) continue;
            else if(!(nY1 < 0 || nX1 < 0 || nY1 >= Y || nX1 >= X) && !(nY2 < 0 || nX2 < 0 || nY2 >= Y || nX2 >= X)){
                if(map[nY1][nX1] == 2 && map[nY2][nX2] == 2) continue;
                else if(map[nY1][nX1] == 2){
                    newNode1.x = tempNode1.x; newNode1.y = tempNode1.y; newNode1.num = tempNode1.num + 1;
                    newNode2.x = nX2; newNode2.y = nY2; newNode2.num = tempNode2.num + 1;
                }
                else if(map[nY2][nX2] == 2){
                    newNode1.x = nX1; newNode1.y = nY1; newNode1.num = tempNode1.num + 1;
                    newNode2.x = tempNode2.x; newNode2.y = tempNode2.y; newNode2.num = tempNode2.num + 1;
                }
                else{
                    newNode1.x = nX1; newNode1.y = nY1; newNode1.num = tempNode1.num + 1;
                    newNode2.x = nX2; newNode2.y = nY2; newNode2.num = tempNode2.num + 1;
                }
                q.push(make_pair(newNode1, newNode2));
            }
            else return tempNode1.num + 1;
        }
    }
    return -1;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> Y >> X;
    char temp;
    node newNode1, newNode2;
    int num = 0 ;

    for(int i = 0 ; i < Y ; i++){
        for(int j = 0 ; j < X ; j++){
            cin >> temp;
            if(temp == '.') map[i][j] = 0;
            else if(temp == '#') map[i][j] = 2;
            else {
                map[i][j] = 0;
                if(num == 0){
                    newNode1.x = j;
                    newNode1.y = i;
                    newNode1.num = 0;
                    num++;
                }
                if(num == 1){
                    newNode2.x = j;
                    newNode2.y = i;
                    newNode2.num = 0;
                }
            }
        }
    }
    q.push(make_pair(newNode1,newNode2));
    cout << BFS() << "\n";
}

평가

문제는 잘 풀었지만, 열번을 넘는 경우라는 말이 10번을 포함하지 않는다라고 인식했는데, 10번을 포함하는 걸로 풀어야 됐었다. 문제를 이해하는 것, 한국말을 이해하는 게 가장 어려운 거 같다.