[백준 13460번] 파이썬 - 구슬탈출2

백준 13460_구슬탈출 2

조건

• 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임
• 보드의 세로 크기는 N, 가로 크기는 M이고 편의상 1x1 크기의 칸으로 나눠져있다.
• 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나있다.
• 이 때, 파란 구슬이 구멍에 들어가면 안 된다.
• 구슬은 중력을 이용해서 이리 저리 굴려야한다.
  • 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울기이와 같은 네 가지 동작이 가능하다.
• 각각의 동작에서 공은 동시에 움직인다.
  • 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패
  • 빨간, 파란 구슬이 동시에 빠져도 실패
  • 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
  • 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
• 보드의 상태가 주어졌을 때, 최소 몇 번만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하시오.

입력

• 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다.
• 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다.
• '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

• 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다.
• 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

접근 방법

• queue에 빨간 구슬의 x, y 좌표, 파란구슬의 x, y 좌표를 넣어준다.
• 방문 여부를 check 배열을 4차원 배열로 선언한다. 배열의 인덱스는 빨간 x, y, 파란 x, y 이다.
• 구슬을 굴리며 다음 위치가 벽이라면 앞으로 가지 못하고 현재 위치가 구멍이라면, 현재 구슬의 색이 무엇인지 판별한다.
• 파란 구슬이라면 무시, 빨간 구슬이라면 cnt 출력
• 구슬을 굴리면서 이동거리를 카운트 해주고, 빨간 구슬과 파란 구슬의 위치가 같다면, 이동 거리를 비교해 겹치지 않게 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  


N, M = map(int, input().split())  

board = []  
for i in range(N):  
    board.append(list(input().rstrip()))  
    for j in range(M):  
        if board[i][j] == 'R':  
            rx, ry = i, j  
        elif board[i][j] == 'B':  
            bx, by = i, j  

di, dj = [0,0,1,-1], [1,-1,0,0]  
def bfs(rx, ry, bx, by):  
    visited = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]  

    q = deque()  
    q.append((rx, ry, bx, by))  
    count = 0  
    while q:  
        for _ in range(len(q)):  
            rx, ry, bx, by = q.popleft()  
            # 움직인 횟수 10회 초과면 -1 출력  
            if count > 10:  
                print(-1)  
                return  

            # 현재 빨간 구슬위치 구멍이면 count  
            if board[rx][ry] == 'O':  
                print(count)  
                return  

            # 4방향 탐색  
            for i in range(4):  
                nrx, nry = rx, ry  
                # 벽 또는 구멍을 만날 때까지  
                while True:  
                    nrx += di[i]  
                    nry += dj[i]  
                    # 벽인 경우 방향 그대로 한칸 뒤로  
                    if board[nrx][nry] == '#':  
                        nrx -= di[i]  
                        nry -= dj[i]  
                        break  
                    if board[nrx][nry] == 'O':  
                        break  
                nbx, nby = bx, by  
                while True:  # #일 때까지 혹은 구멍일 때까지 움직임  
                    nbx += di[i]  
                    nby += dj[i]  
                    if board[nbx][nby] == '#':  # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동  
                        nbx -= di[i]  
                        nby -= dj[i]  
                        break  
                    if board[nbx][nby] == 'O':  
                        break  

                # 파란구슬이 먼저 들어가거나 동시에 들어가면 안됨  
                if board[nbx][nby] == 'O':  
                    continue  
                # 두 구슬의 위치가 같다면 더 많이 이동한 걸 한칸 물려준다.  
                if nrx == nbx and nry == nby:  
                    if abs(nrx-rx) + abs(nry-ry) > abs(nbx-bx) + abs(nby -by):  
                        nrx -= di[i]  
                        nry -= dj[i]  
                    else:  
                        nbx -= di[i]  
                        nby -= dj[i]  

                # 방문 안했다면 추가 후 방문 처리  
                if not visited[nrx][nry][nbx][nby]:  
                    q.append((nrx, nry, nbx, nby))  
                    visited[nrx][nry][nbx][nby] = True  
        count += 1  
    print(-1)  
bfs(rx, ry, bx, by)

• 구현 문제 어렵다.. 손코딩 많이 해보고 생각많이 하기
• visited 를 4중 배열로 체크하는 것이 힘들었다 ㅠ