[알고리즘] 구슬 탈출 시리즈 (구슬 탈출 2)

• 포인트
• bfs를 잘 구할 수 있는가?
• 2개 기준이 있는 맵
• 방문 표시를 하면서 2가지 구슬의 방문을 저장한다.

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

c++/cpp

#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--) { //한 턴에 4가지 방향을 고려하기 위해서 이다.
            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;
            }

            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.push({nxr, nyr, nxb, nyb});
                    visited[nxr][nyr][nxb][nyb] = true;
                }
            }
        }
        if (result == 10) return -1; //10이면 종료를 한다.
        result += 1;
    }
    return -1;
}

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;
}

python

from sys import stdin
from collections import deque

input = stdin.readline


def move(x: int, y: int, dx: int, dy: int) -> tuple:
    cnt = 0

    while data[x + dx][y + dy] != '#' and data[x][y] != 'O':
        # 구멍이 아니고 벽이 아니면 계속 움직인다
        x += dx
        y += dy
        cnt += 1
    return x, y, cnt


def bfs() -> int:
    rx, ry, bx, by = 0, 0, 0, 0
    for i in range(n):
        for j in range(m):
            if data[i][j] == 'R':
                rx, ry = i, j
                # 레드 포인트 정리

            elif data[i][j] == 'B':
                bx, by = i, j
                # 블루 포인트 정리

    q.append([rx, ry, bx, by, 1])
    visited[rx][ry][bx][by] = True

    while q:
        rx, ry, bx, by, cnt = q.popleft()
        if cnt > 10:
            # 문제 조건
            break

        for i in range(4):
            nrx, nry, rcount = move(rx, ry, dx[i], dy[i])
            nbx, nby, bcount = move(bx, by, dx[i], dy[i])

            if data[nbx][nby] == 'O':
                continue

            if data[nrx][nry] == 'O':
                return cnt

            if nrx == nbx and nry == nby:
                if rcount > bcount:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]

            if not visited[nrx][nry][nbx][nby]:
                # visited == 0
                visited[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, cnt + 1))
    return -1


n, m = map(int, input().split())
data = [list(input()) for _ in range(n)]

visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
# bfs 를 하기 위한 방문 표시 배열

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
q = deque()

result = bfs()
print(result)