[백준 13460] 구슬 탈출 2

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

초반에 구슬을 저장할 구조를 따로 만들었다가 낭패를 봤다...설계부터 꼼꼼히 하고 타이핑하는 습관을 가지자.

해결 과정

1. 구슬들의 시작위치를 기록하고 큐에 넣는다.
2. bfs를 하며 4방향으로 굴린다.
   • 한 번에 한 칸씩 움직이는게 아니라 벽을 만날 때 까지 반복해줘야 한다.
3. 빨간 구슬과 파란 구슬이 만났을 때 늦게 온 구슬은 한 칸 뒤로 가게 해줘야 한다.
   • 나는 구슬들이 움직인 거리를 체크하고 더 많이 움직인 구슬(더 뒤에서 시작했다는 말이니깐)을 한 칸 뒤로 뺐다.

구현

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int n, m;
string board[10];


struct pos {
    int i, j;
    pos(int i, int j) : i(i), j(j) {}
};

struct state { // 처음 red와 blue 따로 만들려 했는데, cnt도 넣으려하니 큐가 너무 가독성이 안좋아 만듦
    pos red, blue;
    int cnt;
    state(pos r, pos b, int c) : red(r), blue(b), cnt(c) {}
};

int move(pos& current, int di, int dj) { // 한 방향으로 쭉 나가게끔
    int distance = 0; //움직인 거리
    while (true) {
        int ni = current.i + di;
        int nj = current.j + dj;
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || board[ni][nj] == '#') break;
        current = {ni, nj};
        distance++;
        if (board[ni][nj] == 'O') return -1;  // 구멍에 빠진 경우
    }
    return distance;
}

int main() {
    cin >> n >> m;
    
    // 구슬들의 시작 위치를 저장할 pos
    pos r(-1, -1), b(-1, -1);

    for (int i = 0; i < n; i++) {
        cin >> board[i];
        for (int j = 0; j < m; j++) {
            if (board[i][j] == 'R') r = {i, j};
            if (board[i][j] == 'B') b = {i, j};
        }
    }
    //bfs 구현
    queue<state> q;
    bool visited[10][10][10][10] = {false}; 

    q.push({r, b, 0});
    visited[r.i][r.j][b.i][b.j] = true;

    while (!q.empty()) {
        state current = q.front();
        q.pop();

        if (current.cnt >= 10) break;

        int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : dir) {
            pos newRed = current.red;
            pos newBlue = current.blue;
            // 구슬 움직인 횟수
            int dr = move(newRed, d[0], d[1]); 
            int db = move(newBlue, d[0], d[1]);

            if (db == -1) continue;  // 파란 구슬이 구멍에 빠진 경우
            if (dr == -1) {  // 빨간 구슬이 구멍에 빠진 경우
                cout << current.cnt + 1 << endl;
                return 0;
            }

            if (newRed.i == newBlue.i && newRed.j == newBlue.j) {
                if (dr > db) { //빨간 구슬이 더 많이 움직임 (더 늦게 도착)
                    newRed.i -= d[0];
                    newRed.j -= d[1];
                } else { //파란 구슬이 더 많이 움직임
                    newBlue.i -= d[0];
                    newBlue.j -= d[1];
                }
            }

            if (visited[newRed.i][newRed.j][newBlue.i][newBlue.j]) continue;

            visited[newRed.i][newRed.j][newBlue.i][newBlue.j] = true;
            q.push({newRed, newBlue, current.cnt + 1});
        }
    }

    cout << -1 << endl;
    return 0;
}