[백준] 13460번 구슬 탈출 2

[풀이]

고려해야될 케이스가 많아서 생각보다 애를 먹었던 문제입니다.. ㅠ 

우선 제가 풀이한 방식은 다음과 같습니다.

 

1. 각 지점별로 사방으로 이동을 합니다. 

2. 빨강, 파랑 둘다 '#'를 만나거나 서로 겹치게 되면 멈추고 그 자리를 기억합니다.

   만약 그 중 'O'가 있다면 가능한지 불가능한지 구분해줍니다.

   가능하다면 바로 그 횟수를 출력하면 되고, 불가능하다면 그 위치에서는 더이상 이동 하지 않습니다.

 

여기에서 주의해야 할 부분은 visited를 빨강과 파랑 둘다 기록해줘야 한다는 것입니다.

처음에는 어짜피 빨간색만 구멍에 들어가면 되니까 빨간공만 기록해주면 되지 않을까 하였지만, 

빨간색은 같은 위치인데 파란색의 위치가 달라 결과가 달라지는 경우가 생기더군요.. !

어떻게 보면 BFS로 간단히 풀 수 있는 문제였지만 생각보다 까다로웠던 문제였습니다.

 

아래는 풀이한 코드입니다.

 

#include <iostream>
#include <queue>
using namespace std;
class PosInfo {
public:
    int r_x, r_y, b_x, b_y, move, dir;
    // way => 1 = 아래, 2 = 오, 3 = 위, 4 = 왼
    PosInfo(int r_x, int r_y, int b_x, int b_y, int move, int dir) {
        this->r_x = r_x;
        this->r_y = r_y;
        this->b_x = b_x;
        this->b_y = b_y;
        this->move = move;
        this->dir = dir;
    }
};
char map[10][10];
bool visited[10][10][10][10];
int move(PosInfo &p) {
    bool isR_zero = false;
    bool isB_zero = false;
    while (true) {
        int x1 = p.r_x, x2 = p.b_x, y1 = p.r_y, y2 = p.b_y;
        if (p.dir == 1) { x1--; x2--; }
        else if (p.dir == 2) { y1++; y2++; }
        else if (p.dir == 3) { x1++; x2++; }
        else { y1--; y2--; }
 
        // 둘다 벽이면 break;
        if (map[x1][y1] == '#' && map[x2][y2] == '#') break;
 
        // 지난 자리에 구멍이 있었는지 check
        if (map[x1][y1] == 'O') isR_zero = true;
        if (map[x2][y2] == 'O') isB_zero = true;
 
        // 만약 벽이면 변화된 좌표 원상복구
        if (map[x1][y1] == '#') { x1 = p.r_x; y1 = p.r_y; }
        if (map[x2][y2] == '#') { x2 = p.b_x; y2 = p.b_y; }
 
        // 벽이 아니고 두 구슬이 겹치지 않을 때 좌표 이동
        if (map[x1][y1] != '#' && !(x1 == x2 && y1 == y2)) {
            p.r_x = x1; p.r_y = y1;
        }
        if (map[x2][y2] != '#' && !(x1 == x2 && y1 == y2)) {
            p.b_x = x2; p.b_y = y2;
        }
 
        // 두 구슬이 겹치면 break;
        if (x1 == x2 && y1 == y2)
            break;
    }
 
    // 빨강만 나가면 1
    if (isR_zero && !isB_zero) return 1;
    // 둘다 나가거나 파랑이 나가면 -1
    else if (isR_zero || isB_zero) return -1;
    else return 0;
}
int bfs(PosInfo start, int n, int m) {
    queue<PosInfo> q;
    for (int i = 1; i <= 4; i++) {
        PosInfo pos = start;
        pos.dir = i;
        q.push(pos);
    }
    visited[start.r_x][start.r_y][start.b_x][start.b_y] = true;
    while (!q.empty()) {
        PosInfo pos = q.front();
        q.pop();
        int result = move(pos);
        if (result == 1){
            return pos.move + 1;
        }
        else {
            // move의 결과가 0일 경우와 빨강, 파란공 위치가 이전에 없었던 위치면 q에 추가
            if (!visited[pos.r_x][pos.r_y][pos.b_x][pos.b_y] && result == 0) {
                visited[pos.r_x][pos.r_y][pos.b_x][pos.b_y] = true;
                PosInfo temp = pos;
                temp.move++;
                for (int i = 1; i <= 4; i++) {
                    if (pos.dir != i) {
                        temp.dir = i;
                        q.push(temp);
                    }
                }
            }
        }
    }
    return -1;
}
int main(void) {
    int n, m;
    cin >> n >> m;
    pair<int, int> r_pos, b_pos;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'R') r_pos = { i, j };
            if (map[i][j] == 'B') b_pos = { i, j };
        }
    }
    int result = bfs(PosInfo(r_pos.first, r_pos.second, b_pos.first, b_pos.second, 0, 0), n, m);
    if (result <= 10) cout << result;
    else cout << -1;
    return 0;
}

질문이나 지적사항은 댓글로 남겨주시기 바랍니다 :)