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

골드 Ⅰ

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

13460번: 구슬 탈출 2

 

📄 문제

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

 

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

 

 

---

💡 아이디어

• 구현 문제이다. 주어진 문제의 순서에 따라 구현하면 된다.
• 빨간 구슬과 파란 구슬의 처음 위치를 저장한다.
• 방문 체크를 위해 이동할 때마다 빨간 구슬과 파란 구슬의 위치를 저장한다.
  1. (빨간 구슬의 행과 열 위치, 파란 구슬의 행과 열 위치)의 집합으로 저장하거나,
  2. 빨간 구슬의 행과 열 위치, 파란 구슬의 행과 열 위치를 4차원 배열로 저장한다.
• 두 구슬을 4가지 방향으로 기울이면서 선입선출 형태의 너비 우선 탐색을 수행한다.
• 두 구슬이 이동할 때마다 deq에 (빨간 구슬의 위치, 파란 구슬의 위치, 이동 횟수)를 저장한다.
• 저장된 위치를 꺼내 이어서 탐색할 때는 먼저 이동 횟수가 10을 초과했는지 확인 후 탐색을 수행한다.
• 각 구슬을 같은 방향으로 이동시킨다.
  1. 벽을 만나거나 구멍을 만나면 탐색을 종료한다.
  2. 만나기 바로 전 구슬의 위치와 원래 위치에서 이동한 칸의 개수를 함께 리턴한다.
• 이동 후, 파란 구슬이 구멍에 들어갔는지 확인한다.
• 파란 구슬이 구멍에 들어가는 경우에는 이 위치에 대해 더 이상 탐색을 이어가지 않는다.
• 두 구슬의 위치가 겹쳐지는 경우에는 이동 칸 수가 적은 구슬이 먼저 도착한 것이다.
  
  • 이동 칸이 적은 구슬의 위치는 그대로 둔다.
  • 이동 칸이 많은 구슬의 위치는 한 칸 뒤로 옮겨준다.
  • 이동한 칸의 개수는 각 구슬을 기울여 이동시킬 때 카운트하므로 알 수 있다.
  • 이동할 때 바로 카운트하지 않으면 각 구슬이 이동한 칸을 각각 다시 계산하여 비교해야 한다.

• 두 구슬이 이동한 위치가 방문 안 한 새로운 위치면
  1. 방문 체크를 한다.
  2. 새로운 빨간 구슬의 위치, 파란 구슬의 위치, 이전 이동 횟수 + 1을 저장한다.
• 너비 우선 탐색(BFS)으로
  • 빨간 구슬이 구멍을 만나면 이동 횟수를 리턴한다.
  • 이동 횟수가 10을 초과하거나 deq에 더 이상 저장된 값이 없으면 -1을 리턴하고 탐색을 종료한다.

• 너비 우선 탐색(BFS)의 결과를 출력한다.

 

📝 문제 풀이 (Code)

from collections import deque
import sys
input = sys.stdin.readline

# 구슬 이동
def move(x, y, k):
    # 이동 칸 수 저장
    move_cnt = 0
    # 다음 위치가 벽이거나 현재 위치가 구멍을 만날 때까지 탐색
    while board[x+dx[k]][y+dy[k]] != '#' and board[x][y] != 'O':
        x += dx[k]
        y += dy[k]
        move_cnt += 1
    return x, y, move_cnt


def bfs(rx, ry, bx, by):
    deq = deque()
    # 처음 빨간 구슬의 위치, 파란 구슬의 위치, 이동 횟수 저장
    deq.append((rx, ry, bx, by, 0))
    # 방문체크
    visited = set()
    visited.add((rx, ry, bx, by))
    
    while deq:
        # 빨간 구슬의 위치, 파란 구슬의 위치, 이동 횟수
        rx, ry, bx, by, cnt = deq.popleft()
        # 움직인 횟수가 10회 초과면 -1 출력
        if cnt > 10:
            return -1
        # 빨간 구슬의 위치가 구멍이면 탐색 종료
        if board[rx][ry] == 'O':
            return cnt
        # 4방향 탐색
        for k in range(4):
            # 빨간 구슬 이동
            nrx, nry, rcnt = move(rx, ry, k)
            # 파란 구슬 이동
            nbx, nby, bcnt = move(bx, by, k)
            # 파란 구슬이 구멍에 들어가는 경우 무시
            if board[nbx][nby] == 'O':
                continue
            # 두 구슬의 위치가 같으면 이동거리로 순서 구분
            # 더 많이 이동한 구슬이 더 늦게 도착, 구슬 한칸 뒤로 이동
            if nrx == nbx and nry == nby:
                if rcnt > bcnt:
                    nrx -= dx[k]
                    nry -= dy[k]
                else:
                    nbx -= dx[k]
                    nby -= dy[k]
            # 방문 체크
            if (nrx, nry, nbx, nby) not in visited:
                visited.add((nrx, nry, nbx, nby))
                deq.append((nrx, nry, nbx, nby, cnt+1))
    return -1


n, m = map(int, input().split())
board = []
for i in range(n):
    arr = list(input())
    board.append(arr)
    for j in range(m):
        # 빨간 구슬 위치 찾기
        if arr[j] == 'R':
            ri, rj = i, j
        # 파란 구슬 위치 찾기
        elif arr[j] == 'B':
            bi, bj = i, j

# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]

print(bfs(ri, rj, bi, bj))