[BOJ/백준] 13459 구슬 탈출 파이썬

문제 링크 : https://www.acmicpc.net/problem/13459

13459번: 구슬 탈출

 

BFS로 풀면 된다는 것은 간단하게 캐치 할 수 있다.

하지만 단순히 2차원 배열가지고 해결하기에는 힘들다. 할 수 있는지도 잘 모르겠다.

핵심은 각 구슬의 위치를 동시에 가지고 가야한다는 것이다. 그렇기 때문에 방문 체크도 동시에 해야한다.

따라서 방문배열를 4차원으로 같은 시점의 빨간공, 파란공의 좌표를 동시에 체크해줘야한다.

이부분만 잘 처리한다면 어렵지 않게 풀 수 있다.

 

구슬 움직임의 경우 그 방향으로 쭉가다가 벽이나 범위 밖이라면 좌표를 하나씩 빼고 이동한 칸을 반환 시켜줬다.

만약 두 구슬이 같은 위치에 올 경우 이동한 칸의 개수가지고 누가 먼저 온 것인지 판별한다.

이동한 칸수가 더 크다면 그만큼 더 멀리서 온 것이므로 해당 색의 공 좌표를 하나씩 빼준다.

 

그리고 파란공이 구멍에 빠지면 게임은 끝나므로 파란공 먼저 이동시키고 구멍에 빠지는지 체크한다.

 

from sys import stdin
from collections import deque

dx = [-1,1,0,0]
dy = [0,0,-1,1]
input = stdin.readline

n,m = map(int, input().split())
board = []

srx=sry=sbx=sby=-1
for x in range(n):
    board.append(list(input().strip()))
    for y in range(m):
        if board[x][y] == 'R':
            srx,sry = x,y
        elif board[x][y] == 'B':
            sbx,sby = x,y

def solv():
    visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
    q = deque([(srx,sry,sbx,sby,0)])

    visited[srx][sry][sbx][sby] = True
    while q:
        rx,ry,bx,by,cnt = q.pop()

        if board[rx][ry] == 'O':
            print(1)
            return

        if cnt == 10:
            continue

        for d in range(4):
            nbx,nby,bcnt = move_ball(bx,by,d)
            if board[nbx][nby] == 'O':
                continue

            nrx,nry,rcnt = move_ball(rx,ry,d)

            if nrx == nbx and nry == nby:
                if bcnt > rcnt:
                    nbx -= dx[d]
                    nby -= dy[d]
                else:
                    nrx -= dx[d]
                    nry -= dy[d]

            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                q.appendleft((nrx,nry,nbx,nby,cnt+1))
    print(0)
def move_ball(x,y,d):
    cnt = 0
    while True:
        x += dx[d]
        y += dy[d]
        if not point_validator(x,y):
            x -= dx[d]
            y -= dy[d]
            return x,y,cnt
        if board[x][y] == 'O':
            return x,y,cnt
        cnt += 1

def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= m:
        return False
    elif board[x][y] == '#':
        return False
    return True

solv()