[백준] 13459번 구슬 탈출

조건

파란 구슬이 구멍에 빠져서는 안된다.

파란 구슬과 빨간 구슬이 동시에 빠져서도 안된다.

빨간 구슬과 파란 구슬이 동시에 움직이고, 굴리면 벽에 부딪힐 때까지 굴러간다.

구슬 2개가 동시에 움직이기 떄문에, 4차원 배열을 통해 방문 여부를 체킹해주면 편하다.

구동 순서

• 초기화 진행한다.

  • q에 빨간 구슬의 (x,y)좌표와 파랑구슬의 (x,y) 좌표가 전부 들어간다.

  • 방문 여부를 확인할 check 배열을 4차원 배열로 표현해준다.

    • 배열의 인덱스는 빨간x 빨간y 파랑x 파랑y 이다.

• 구슬을 상하좌우로 굴려본다.

  • 구슬을 굴릴 때, 구슬의 다음 위치가 벽인지, 구슬의 현재 위치가 구멍인지 확인한다.

  • 구슬의 다음위치가 벽이라면, 앞으로 가지 못한다.

  • 구슬의 현재 위치가 구멍이라면, 현재 구슬의 색이 무슨 색인지 판별한다.

    • 만약 파란 구슬의 현재 위치가 구멍이라면 무시하고 다음 방향으로 넘어간다.

    • 빨간 구슬의 현재 위치가 구멍이라면, 1을 출력하고 종료한다.

  • 구슬을 굴리면서, 빨간 구슬의 이동 거리와 파랑 구슬의 이동 거리를 카운트 해야한다.

    • 구슬을 굴린 후, 빨간 구슬의 위치와 파란 구슬의 위치가 같다면, 이동 거리 비교를 통해 겹치지 않도록 처리해야 한다.

    • 만약 구슬이 곂쳤다면, 굴릴 때 카운트했던 이동 거리가 더 긴 구슬의 위치를 한칸 이전으로 되돌린다

  • 굴리는 과정이 10번을 넘어가면 그대로 종료하고, 0을 출력한다

  • 더이상 갈 곳이 없을 때는 bfs를 빠져나와서 0 을 출력한다.

from sys import stdin
import sys
from collections import deque

# input = stdin.readline
sys.stdin = open('1.txt')
n, m = map(int, input().split())
a = [list(input().strip()) for _ in range(n)]
check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()

def init():
    rx, ry, bx, by = [0]*4
    for i in range(n):
        for j in range(m):
            if a[i][j]=='R':
                rx,ry = i,j
            if a[i][j]=='B':
                bx,by = i,j
    q.append((rx,ry,bx,by,0))
    check[rx][ry][bx][by]=True

def move(x,y,dx,dy,c):
    while a[x+dx][y+dy] != '#' and a[x][y] != 'O':
        x+=dx
        y+=dy
        c+=1
    return x,y,c

def bfs():
    while q:
        red_x,red_y,blue_x,blue_y,c = q.popleft()
        if c >= 10:         # 카운트가 10회 이상인지 확인해보자
            break
        for i in range(4):
            next_red_x, next_red_y, red_c = move(red_x, red_y, dx[i], dy[i], 0)
            next_blue_x, next_blue_y, blue_c = move(blue_x, blue_y, dx[i], dy[i], 0)
            if a[next_blue_x][next_blue_y] == 'O':
                continue
            if a[next_red_x][next_red_y] == 'O':
                print(c+1)
                return
            # 만약에 이동 한 빨강과 파랑의 위치가 같다면? 곂치면 안되기 떄문에 이동
            # 이슈가 생김
            if next_red_x == next_blue_x and next_red_y == next_blue_y:
                if red_c > blue_c:
                    next_red_x, next_red_y = next_red_x-dx[i], next_red_y-dy[i]
                else:
                    next_blue_x, next_blue_y = next_blue_x-dx[i], next_blue_y-dy[i]
            if not check[next_red_x][next_red_y][next_blue_x][next_blue_y]:
                check[next_red_x][next_red_y][next_blue_x][next_blue_y] = True
                q.append((next_red_x, next_red_y, next_blue_x, next_blue_y, c+1))
    print(-1)

init()
bfs()