[백준]두동전

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

16197번: 두 동전

문제를 읽었을 때 구슬탈출2와 굉장히 비슷한 느낌을 받았다.

최소 횟수를 구해주기 때문에 bfs를 사용했고, 2개의 구슬의 위치관계를 확인해야해서 4차배열을 선언했다.

XOR연산(^)을 처음 사용해봤다.

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct INFO {
    int r1, c1, r2, c2;
};
 
int N, M;
char map[20][20];
queue<INFO> q;
int or1, oc1, or2, oc2;
bool isV[20][20][20][20];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
 
bool InRange(int r, int c) {
    if (r < 0 || c < 0 || r >= N || c >= M) return false;
    else return true;
}
 
bool isWall(int r, int c) {
    if (map[r][c] == '#') return true;
    else return false;
}
 
void solve() {
    int cnt = 1;
    while (!q.empty()) {
        int qlen = q.size();
        while (qlen--) { //단계별로 10번 반복하기 위해서
            int r1 = q.front().r1, c1 = q.front().c1, r2 = q.front().r2, c2 = q.front().c2; q.pop();
            for (int i = 0; i < 4; i++) {
                int nr1 = r1 + dr[i], nr2 = r2 + dr[i];
                int nc1 = c1 + dc[i], nc2 = c2 + dc[i];
                
                //벽이면 후진.
                if (isWall(nr1, nc1)) {nr1-=dr[i];nc1-=dc[i];}
                if (isWall(nr2, nc2)) {nr2-=dr[i],nc2-=dc[i];}
 
                if (!InRange(nr1, nc1) && !InRange(nr2, nc2)) continue; //둘다 나가면 무시
                if (InRange(nr1, nc1) ^ InRange(nr2, nc2)) { printf("%d\n", cnt); return; } //성공
                if (isV[nr1][nc1][nr2][nc2]) continue; //방문했으면 패스
                
                isV[nr1][nc1][nr2][nc2] = true;
                q.push({ nr1,nc1,nr2,nc2 });
            }
        }
        cnt++;
        if (cnt >= 11) { printf("-1\n"); return; } //10번넘어도 안되면 실패
    }
    printf("-1\n"); //10번 전에 이미 실패
}
 
int main()
{
    int cnt = 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' && cnt == 0) { or1 = i; oc1 = j; cnt++; } //동전 flag를 통해 2개입력
            if (map[i][j] == 'o' && cnt == 1) { or2 = i; oc2 = j; }
        }
    }
    isV[or1][oc1][or2][oc2] = true; //bfs시작점
    q.push({ or1,oc1,or2,oc2 });
    solve();
    
    return 0;
}