[알고리즘] c++ cpp 구슬탈출 시리즈 (구슬탈출1)

포인트

1. bfs를 잘 할 수 있는가?

2. 조건을 이해할 수 있는가?

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int n, m;
char map[11][11];
bool visited[11][11][11][11];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int rx, ry, bx, by;

int bfs() {

    queue<tuple<int, int, int, int>> q;
    q.emplace(rx, ry, bx, by);
    visited[rx][ry][bx][by] = true;
    int result = 0;

    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            int xr, yr, xb, yb;
            tie(xr, yr, xb, yb) = q.front();
            q.pop();

            if (map[xr][yr] == 'O' && map[xr][yr] != map[xb][yb]) {
//                return result;
                return 1;
            }

            for (int i = 0; i < 4; i++) {
                int nxr = xr;
                int nyr = yr;
                int nxb = xb;
                int nyb = yb;

                while (map[nxr + dx[i]][nyr + dy[i]] != '#' && map[nxr][nyr] != 'O') {
                    nxr += dx[i];
                    nyr += dy[i];
                }

                while (map[nxb + dx[i]][nyb + dy[i]] != '#' && map[nxb][nyb] != 'O') {
                    nxb += dx[i];
                    nyb += dy[i];
                }

                if (nxr == nxb && nyr == nyb) {
                    if (map[nxr][nyb] == 'O') continue;
                    if (abs(nxr - xr) + abs(nyr - yr) <
                        abs(nxb - xb) + abs(nyb - yb)) {
                        nxb -= dx[i];
                        nyb -= dy[i];
                    } else {
                        nxr -= dx[i];
                        nyr -= dy[i];
                    }
                }
                if (!visited[nxr][nyr][nxb][nyb]) {
                    q.emplace(nxr, nyr, nxb, nyb);
                    visited[nxr][nyr][nxb][nyb] = true;
                }
            }
        }
        if (result == 10) return 0; //10이면 종료를 한다.
        result += 1;
    }
    return 0;
}

int main() {
    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') {
                rx = i;
                ry = j;
            } else if (map[i][j] == 'B') {
                bx = i;
                by = j;
            }
        }
    }
    cout << bfs();
    return 0;
}