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

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

13459번: 구슬 탈출

Problem

• 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

조건

• 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다.
• 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다.
• 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
• 각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
• 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

SOL

구현해야할 조건들이 꽤 많다. 구현 문제는 항상 천천~히 하나씩 조건을 생각해주면서 구현해나아가야 한다.

 

전체적인 풀이는 BFS 길찾기 탐색을 할거다.

• 빨간 구슬의 위치, 파란 구슬의 위치를 받아온 후,deque에 넣을거다. BFS 탐색 시, 무한루프를 돌면 안되므로 visited배열도 선언해줄거다.
• 하지만, 빨간 구슬과 파란구슬이 동시에 움직이므로, 한꺼번에 처리가 되어야한다. visited를 빨강구슬,파랑구슬 따로 구현하지 말고, 빨강/파랑 함께 묶어서 4차원 배열로 선언하자.
• 파랑구슬이 구멍에 들어가는 경우는, 어떤 경우라도 실패하므로, 파랑구슬이 구멍에 들어가지 않는 경우만 생각해준다.
  • move 함수가 선형적인 움직임이 아니므로, 따로 구현해보자. (이게 더 편해서, 난 이렇게 했다. 선형적인 움직임을 가지고 있다면, for 밑에 바로 구현하는 편, 이건 취향차이)
  • 구슬이 겹칠 때, 구슬을 처리하는 부분이 있어야한다.
• 시행 횟수가 10번이 넘거나, dq를 다 소진했는데도 탈출을 못했다면, 해당 조건내에서는 탈출을 못하므로, print("0")을 해준다.

# 구현
from collections import deque
import sys
input = sys.stdin.readline
dx=(0,1,0,-1)
dy=(1,0,-1,0)

N,M =map(int,input().split())
board = [input().rstrip() for _ in range(N)]
#방문 배열을 4차원 배열로 관리
visited=[[[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N)]

#print(board)

# 굴리는 개념, 선형적인 탐색이 아님. 벽을 만나거나, 구멍을 만날 때 까지 굴려야함.
def moving(y,x,dy,dx):
    d=0
    while board[y+dy][x+dx] !="#" and board[y][x] !="O":
        y+=dy
        x+=dx
        d+=1
    return y,x,d

def solve():
    while dq:
        ry,rx,by,bx,d=dq.popleft()
        if d>10:
            break
        for k in range(4):
            nry,nrx,rd = moving(ry,rx,dy[k],dx[k])
            nby,nbx,bd = moving(by,bx,dy[k],dx[k])
            #블루가 구멍에 들어가는 경우는 어떠한 경우라도 실패임!
            if board[nby][nbx] !="O":
                if board[nry][nrx] =="O":
                    print("1")
                    return
                #구슬이 겹치는 경우
                if nry==nby and nrx ==nbx:
                    # 빨간 구슬이 나중에 도착한 경우
                    if rd>bd:
                        nry -=dy[k]
                        nrx -=dx[k]
                    # 빨간 구슬이 먼저 도착한 경우
                    else:
                        nby -=dy[k]
                        nbx -=dx[k]
                if not visited[nry][nrx][nby][nbx]:
                    visited[nry][nrx][nby][nbx] = True
                    dq.append([nry,nrx,nby,nbx,d+1])
    print("0")

dq =deque()

for i in range(N):
    for j in range(M):
        if board[i][j] =="R":
            ry,rx =i,j
        if board[i][j] =="B":
            by,bx=i,j

dq.append([ry,rx,by,bx,1])
visited[ry][rx][by][bx] = True
solve()