백준(boj) 13460_구슬 탈출2 (파이썬, c++)

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

풀이

---

빨간 구슬과 파란 구슬이 있다. 네 방향으로 기울일 수 있는데 한번 기울이면 구슬이 벽에 닿거나 구멍에 빠질 때까지 이동한다. 파란 구슬은 어떠한 상황에도 빠지면 안 되고, 빨간 구슬만 구멍으로 들어갔을 때 게임이 끝난다. 최소 몇 번 만에 빨간 구슬을 빼낼 수 있을까 찾는 문제이다. 단, 10번을 초과하면 -1을 출력한다. BFS를 사용해서 최단 거리를 찾아주었고, move() 함수를 통해 기울이는 동작을 구현했다. visit 배열을 4차원으로 선언해서 빨간구슬, 파란구슬 각각의 x, y 값이 위치한 곳에 방문 순서를 기록해 두었다.

python3

from sys import*
from collections import*
input = lambda: stdin.readline().strip()
​
def move(x, y, dx, dy):              #기울이기
    cnt = 0
    while 1:
        nx, ny = x+dx, y+dy
        cnt+=1
        if a[nx][ny]=='O':            #구멍에 빠지면 그 칸
            return (nx, ny, cnt)
        elif a[nx][ny]=='#':          #벽에 닿으면 그 전칸
            return (x, y, cnt-1)
        x, y = nx, ny
def bfs():  
    while q:
        rx, ry, bx, by = q.popleft()
        if visit[rx][ry][bx][by]>10:continue
        if a[rx][ry]=='O': return visit[rx][ry][bx][by]    #빨간색이 구멍에 빠지면 끝
        for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
            nrx, nry, nrd = move(rx, ry, dx, dy)
            nbx, nby, nbd = move(bx, by, dx, dy)
            if a[nbx][nby] == 'O': continue                #파란색 빠지는건 여기서 처리
            if nrx == nbx and nry == nby:                  #두 개 겹치면 늦게온 친구 한 칸 뒤로
                if nrd > nbd:
                    nrx, nry = nrx-dx, nry-dy
                else:
                    nbx, nby = nbx-dx, nby-dy
            #if a[nrx][nry]=='O': 이 값이 10 넘어갈수도 있잖아... 맨날틀려 진짜
            #   return visit[rx][ry][bx][by]+1
            if visit[nrx][nry][nbx][nby] != -1:continue
            visit[nrx][nry][nbx][nby]=visit[rx][ry][bx][by]+1
            q.append((nrx, nry, nbx, nby))
    return -1
n,m=map(int,input().split())
a=[input()for _ in range(n)]
visit = [[[[-1]*m for _ in range(n)]for _ in range(m)] for _ in range(n)]
for i in range(n):
    for j in range(m):
        if a[i][j]=='R':
            rx, ry = i, j
        elif a[i][j]=='B':
            bx, by = i, j
​
visit[rx][ry][bx][by]=0
q=deque()
q.append((rx, ry, bx, by))
print(bfs())

C++

#include<cstdio>
#include<tuple>
#include<memory.h>
#include<queue>
​
using namespace std;
typedef tuple<int, int, int, int> T;
typedef tuple<int, int, int> TR;
const int SIZE = 11;
int visit[SIZE][SIZE][SIZE][SIZE];
char a[SIZE][SIZE];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int rx, ry, bx, by;
TR move(int x, int y, int dx, int dy){
    int cnt = 0;
    int nx, ny;
    while(1){
        nx = x+dx, ny = y+dy;
        cnt++;
        if(a[nx][ny]=='O') return make_tuple(nx, ny, cnt);
        else if (a[nx][ny]=='#') return make_tuple(x, y, cnt-1);
        x = nx, y = ny;
    }
}
​
int bfs(){
    queue<T> q;
    q.push(make_tuple(rx, ry, bx, by));
    visit[rx][ry][bx][by] = 0;
    while(!q.empty()){
        tie(rx, ry, bx, by) = q.front();
        q.pop();
        if(visit[rx][ry][bx][by]>10) continue;
        if(a[rx][ry]=='O') return visit[rx][ry][bx][by];
        for(int i=0; i<4; i++){
            int nrx, nry, nrd, nbx, nby, nbd;
            tie(nrx, nry, nrd) = move(rx, ry, dx[i], dy[i]);
            tie(nbx, nby, nbd) = move(bx, by, dx[i], dy[i]);
            if (a[nbx][nby] == 'O') continue;
            if (nrx == nbx && nry == nby){
                if(nrd > nbd) nrx = nrx-dx[i], nry = nry-dy[i];
                else nbx = nbx-dx[i], nby = nby-dy[i];
            }
            if(visit[nrx][nry][nbx][nby] != -1) continue;
            visit[nrx][nry][nbx][nby]=visit[rx][ry][bx][by]+1;
            q.push(make_tuple(nrx, nry, nbx, nby));
        }
    }
    return -1;
}
​
int main(){
    int n,m;
    scanf("%d %d",&n, &m);
    for(int i=0; i<n; i++){
        scanf("%s", &a[i]);
        for(int j=0; j<m; j++){
            if(a[i][j]=='R'){
                rx = i, ry = j;
            }
            else if(a[i][j]=='B'){
                bx = i, by = j;
            }
        }
    }
    memset(visit, -1, sizeof(visit));
    printf("%d", bfs());
    return 0;
}

고찰

---

python 29번째 줄 같은 실수를 너무 자주한다...