[백준 13460번] 구슬 탈출 2 (파이썬/python)

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

13460번: 구슬 탈출 2

 

너무.. 어려웠다........ 그래서 다른 분의 풀이를 참고했다.

 

구슬을 굴린다. 빨간구슬과 파란구슬을 동시에 움직인다.

구슬 위치의 상관관계를 빼고 구슬을 동시에 굴리게 구현하고

빨간구슬과 파란구슬이 겹쳐져있는 상태라면 

더 많이 이동한 구슬을 뒤로 1칸 빼준다.

 

한번의 기울이기에서 파란구슬이 빠지는 경우가 있을경우 그 경우는 continue 처리한다.

빨간 구슬만 빠지는 경우 몇 번 기울였는지 출력해준다.

혹시 10번 도전했는데 실패할경우 -1을 프린트해주고 함수를 종료한다.

 

 

import sys
from collections import deque
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
arr = [list(input().strip()) for i in range(n)]
visit = [[[[0] * m for i in range(n)] for j in range(m)] for k in range(n)]
q = deque()
# 빨강, 파랑, 구멍 순
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 'R':
            rx, ry = i, j
        elif arr[i][j] == 'B':
            bx, by = i, j
 
# 빨간좌표, 파란좌표, 몇 번째 기울이는건지
q.append([rx, ry, bx, by, 1])
visit[rx][ry][bx][by] = 1
 
 
def move(x, y, i, j):
    count = 0
    # 다음 이동하는 벽이 구멍이 아니거나 #이 아닐때까지
    while arr[x + i][y + j] != '#' and arr[x][y] != 'O':
        x += i
        y += j
        count += 1
 
    return x, y, count
 
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
 
def bfs():
    while q:
        rx, ry, bx, by, cnt = q.popleft()
        if cnt > 10:
            break
        for i in range(4):
            # 기울였을때 끝까지 간 상태를 나타냄
            nrx, nry, r_cnt = move(rx, ry, dx[i], dy[i])
            nbx, nby, b_cnt = move(bx, by, dx[i], dy[i])
 
            # 파란 구슬이 구멍에 떨어지면
            if arr[nbx][nby] == 'O':
                continue
            # 성공조건
            if arr[nrx][nry] == 'O':
                print(cnt)
                return
            # 둘이 겹쳐있을경우 더 많이 이동한녀석을 1칸 뒤로 물려줌
            if nrx == nbx and nry == nby:
                if r_cnt > b_cnt:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
            if visit[nrx][nry][nbx][nby] == 0:
                visit[nrx][nry][nbx][nby] = 1
                q.append([nrx, nry, nbx, nby, cnt + 1])
 
    print(-1)
    return
 
 
bfs()