백준 13460번 구슬 탈출 2 C++

출처 : https://www.acmicpc.net/problem/13460

 

두 구슬이 같은 행이나 열에 있을때 어떤 구슬을 먼저 굴려야 하는지와 구슬이 빠지는 경우들을 잘 고려해서 구현하면 된다. 빨간 구슬과 파란 구슬 두 좌표의 범위가 크지 않기 때문에 좌표를 해시값으로 바꿔서 2차원 배열로 방문표시를 했다.

 

내 코드에서는 어떤 구슬을 먼저 굴려야 하는지에 대한 부분이 좀 더럽게 짜여져있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, m;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

struct Info {
    int redHash;
    int blueHash;
    int moveCnt;
};

vector<vector<char>> board;
vector<vector<bool>> found;
pair<int, int> startRedPos;
pair<int, int> startBluePos;
pair<int, int> targetPos;

int Pos2Hash(pair<int,int> pos) {
    return pos.first * 10 + pos.second;
}

pair<int, int> Hash2Pos(int hash) {
    int row = hash / 10;
    int col = hash % 10;
    return { row,col };
}

enum BeadColor {
    RED,
    BLUE
};

pair<int, pair<int,int>> MoveBead(int dir, pair<int, int> pos, BeadColor color) {
    int ret = 0;
    int row = pos.first;
    int col = pos.second;
    while (true) {
        int nextRow = row + dRow[dir];
        int nextCol = col + dCol[dir];
        if (board[nextRow][nextCol] == 'O') {
            if (color == RED) ret = 1;
            if (color == BLUE) ret = 2;
            break;
        }
        if (board[nextRow][nextCol] != '.') break;
        row = nextRow;
        col = nextCol;
    }
    return { ret,{row,col} };
}

// 0 : 둘다 안빠지고 도착
// 1 : 빨강만 빠짐
// 2 : 파랑만 빠짐
// 3 : 둘다 빠짐
pair<int,pair<int,int>> MoveBead(int dir, pair<int, int> redPos, pair<int, int> bluePos) {
    int redBead = 0;
    int blueBead = 0;
    pair<int, int> retRedPos = { -1,-1 };
    pair<int, int> retBluePos = { -1,-1 };
    pair<int, pair<int, int>> res;
    if (dir == 0) {
        if (redPos.first <= bluePos.first) {
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = 'R';
            }
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = '.';
            }
        }
        else {
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = 'B';
            }
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = '.';
            }
        }
    }
    else if (dir == 1) {
        if (redPos.second >= bluePos.second) {
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = 'R';
            }
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = '.';
            }
        }
        else {
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = 'B';
            }
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = '.';
            }
        }
    }
    else if (dir == 2) {
        if (redPos.first >= bluePos.first) {
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = 'R';
            }
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = '.';
            }
        }
        else {
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = 'B';
            }
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = '.';
            }
        }
    }
    else if (dir == 3) {
        if (redPos.second <= bluePos.second) {
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = 'R';
            }
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (redBead == 0) {
                board[retRedPos.first][retRedPos.second] = '.';
            }
        }
        else {
            res = MoveBead(dir, bluePos, BLUE);
            blueBead = res.first;
            retBluePos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = 'B';
            }
            res = MoveBead(dir, redPos, RED);
            redBead = res.first;
            retRedPos = res.second;
            if (blueBead == 0) {
                board[retBluePos.first][retBluePos.second] = '.';
            }
        }
    }
    int retRedHash = Pos2Hash(retRedPos);
    int retBlueHash = Pos2Hash(retBluePos);

    return { redBead + blueBead,{retRedHash,retBlueHash} };
}

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

    found = vector<vector<bool>>(100, vector<bool>(100, false));

    cin >> n >> m;
    board = vector<vector<char>>(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            board[i][j] = str[j];
            if (board[i][j] == 'R') {
                startRedPos = ::make_pair(i, j);
                board[i][j] = '.';
            }
            else if (board[i][j] == 'B') {
                startBluePos = ::make_pair(i, j);
                board[i][j] = '.';
            }
            else if (board[i][j] == 'O') targetPos = ::make_pair(i, j);
        }
    }
    int startRedHash = Pos2Hash(startRedPos);
    int startBlueHash = Pos2Hash(startBluePos);
    queue<Info> q;
    q.push({ startRedHash, startBlueHash, 0 });
    found[startRedHash][startBlueHash] = true;

    int ans = -1;

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        if (curr.moveCnt >= 10)
            break;

        pair<int, int> currRedPos = Hash2Pos(curr.redHash);
        pair<int, int> currBluePos = Hash2Pos(curr.blueHash);
        int nextMoveCnt = curr.moveCnt + 1;
        bool isAns = false;
        for (int i = 0; i < 4; i++) {
            auto res = MoveBead(i, currRedPos, currBluePos);
            if (res.first == 1) {
                ans = nextMoveCnt;
                isAns = true;
                break;
            }
            if (res.first == 2 || res.first == 3) continue;
            int redHash = res.second.first;
            int blueHash = res.second.second;
            if (found[redHash][blueHash]) continue;
            q.push({ redHash,blueHash,nextMoveCnt });
            found[redHash][blueHash] = true;
        }
        if (isAns) break;
    }
    cout << ans;
}