[백준] 13460 구슬 탈출 2

13460번: 구슬 탈출 2

 

www.acmicpc.net

풀이

BFS를 사용하여 해결할 수 있는 문제이다. 이 때 신경써야 할 좌표가 빨간공의 x, y좌표와 파란공의 x, y좌표로 총 4개이다. 따라서 중복체크를 위한 배열을 visited[red.y][red.x][blue.y][blue.x]로 4차원으로 선언하여 해결하였다.

##

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

struct Ball {
    int x, y;
};

int n, m;
char map[10][11];
bool visited[10][10][10][10];
Ball red, blue;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };

int bfs() {
    queue<pair<pair<Ball, Ball>, int>> q;
    q.push({ { red, blue }, 0 });
    visited[red.y][red.x][blue.y][blue.x] = true;

    while (!q.empty()) {
        Ball cur_red = q.front().first.first;
        Ball cur_blue = q.front().first.second;
        int cnt = q.front().second;
        if (cnt >= 10) break;
        q.pop();

        // 4방향으로 기울이기
        for (int i = 0; i < 4; i++) {
            int rx = cur_red.x; int ry = cur_red.y;
            int bx = cur_blue.x; int by = cur_blue.y;

            // 빨간공 이동
            while (true) {
                rx += dx[i]; ry += dy[i];
                // 구멍에 들어간 경우
                if (map[ry][rx] == 'O') break;
                // 벽과 같은 위치에 있으면 반대방향으로 1칸 이동
                if (map[ry][rx] == '#') {
                    rx -= dx[i]; ry -= dy[i];
                    break;
                }
            }

            // 파란공 이동
            while (true) {
                bx += dx[i]; by += dy[i];
                // 구멍에 들어간 경우
                if (map[by][bx] == 'O') break;
                // 벽과 같은 위치에 있으면 반대방향으로 1칸 이동
                if (map[by][bx] == '#') {
                    bx -= dx[i]; by -= dy[i];
                    break;
                }
            }

            // 파란공이 구멍에 들어간 경우
            if (map[by][bx] == 'O') continue;
            // 파란공이 구멍에 들어가지 않고, 빨간공만 들어간 경우
            else if (map[ry][rx] == 'O') return cnt + 1;

            // 파란공과 빨간공이 같은 위치에 있는 경우
            if (rx == bx && ry == by) {
                // 처음에 위치에서 빨간공이 더 멀리 이동했으므로 반대 방향으로 한칸 이동시킨다
                if (abs(cur_red.x - rx) + abs(cur_red.y - ry) > abs(cur_blue.x - bx) + abs(cur_blue.y - by)) {
                    rx -= dx[i]; ry -= dy[i];
                }
                // 처음에 위치에서 파란공이 더 멀리 이동했으므로 반대 방향으로 한칸 이동시킨다
                else {
                    bx -= dx[i]; by -= dy[i];
                }
            }
            if (!visited[ry][rx][by][bx]) {
                visited[ry][rx][by][bx] = true;
                q.push({ {{rx, ry}, {bx, by}}, cnt + 1 });
            }
        }
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(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] == 'R') {
                red.x = j; 
                red.y = i;
            }
            if (map[i][j] == 'B') {
                blue.x = j; 
                blue.y = i;
            }
        }
    }
    cout << bfs() << '\n';
    return 0;
}