[백준/BOJ] 16197번 두 동전 (C++)

www.acmicpc.net/problem/16197

16197번: 두 동전

13460번과 비슷한 BFS 유형의 문제입니다.

두 동전이 동시에 움직이는 것을 처리해주기 위해서, visit배열을 4차원 배열을 두어 각 동전의 움직임을 기록합니다. 그리고 큐에도 두 동전의 좌표와 버튼을 누른 수를 넣으며 BFS 탐색을 해주기 위해서 구조체를 선언하였습니다. 그 다음 문제풀이를 위한 순서는 다음과 같습니다.

 

1. 위, 오른쪽, 아래, 왼쪽 방향마다 동전이 하나만 떨어지는 경우 체크

2. 동전이 둘 다 떨어지는 경우 체크

3. 이미 방문한 적이 있는지 체크

4. 처음 방문한 곳이고, 만약 벽에 부딪히는 구슬이 있다면 그 구슬의 좌표를 갱신

5. 종료 조건을 만날 때 까지 계속 위의 과정을 반복

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, r1, c1, r2, c2;
char map[21][21];
bool visit[21][21][21][21];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

struct Coin {
    int x1, y1, x2, y2, cnt; // 두 동전의 좌표, 버튼을 누른 수
};

bool isIn(int x, int y) {
    if(x < 0 || x >= n || y < 0 || y >= m) return false;
    return true;
}

int BFS() {
    queue<Coin> q;
    q.push({ r1, c1, r2, c2, 0 });
    visit[r1][c1][r2][c2] = true;
    
    while(!q.empty()) {
        auto now = q.front();
        q.pop();
        
        if(now.cnt > 10) return -1; // 버튼을 누른 수가 10이 넘은 경우 (종료)
        
        for(int i = 0; i < 4; i++) {
            int nx1 = now.x1 + dx[i];
            int ny1 = now.y1 + dy[i];
            int nx2 = now.x2 + dx[i];
            int ny2 = now.y2 + dy[i];
            
            // 동전이 하나만 떨어지는 경우 (종료)
            if( (!isIn(nx1, ny1) && isIn(nx2, ny2)) || (isIn(nx1, ny1) && !isIn(nx2, ny2)) ) {
            	if(now.cnt + 1 > 10) return -1; // cnt가 10인 경우, 11이 되면 안되므로 따로 예외처리
            	return now.cnt + 1;
			}
            
            // 동전이 둘 다 떨어지는 경우
            if(!isIn(nx1, ny1) && !isIn(nx2, ny2)) continue;
            // 이미 방문한 좌표인 경우
            if(visit[nx1][ny1][nx2][ny2]) continue;
            
            // 벽에 부딪히는 경우 좌표 갱신
            if(map[nx1][ny1] == '#') nx1 = now.x1, ny1 = now.y1;
            if(map[nx2][ny2] == '#') nx2 = now.x2, ny2 = now.y2;
            
            q.push({ nx1, ny1, nx2, ny2, now.cnt + 1 });
            visit[nx1][ny1][nx2][ny2] = true;
        }
    }
    
    return -1;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int chk = 0;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> map[i][j];
            if(map[i][j] == 'o') {
                if(chk == 0) r1 = i, c1 = j, chk++;
                else r2 = i, c2 = j;
            }
        }
    }
    
    cout << BFS();
}