[백준] 13460번: 구슬 탈출 2

문제

백준 - 13460번: 구슬 탈출 2

분석

게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. (파란 구슬은 빼면 실패)
네 방향으로 기울이는 동작이 가능하고, 기울이기를 통해 구슬을 움직인다. (구슬이 더 이상 안움직이면 기울이기를 멈춤)
최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 문제이다.

알고리즘 없이 깡구현(?)만으로 시도했다가 나중에 디버깅도 어렵고 코드가 난해해져서 실패했었다.
인터넷 서칭을 통해 힌트를 얻고 다시 풀었다.

이 문제에서 방문처리는 두 구슬의 위치를 모두 고려한다. 즉, 두 구슬이 모두 이전에 있었던 위치에 놓인 상황인 경우가 아니라면 다 재방문이 가능하다.
이를 구현하기 위해 4차원 배열을 초기화했다.

bfs 알고리즘을 통해 최소 동작 횟수를 구할 수 있다.
큐에 두 구슬의 위치와 현재 동작 횟수 정보를 넣고 시작한다.

문제에서 동작 횟수가 10이하가 아닌 경우 -1을 출력한다고 했으므로 move가 10보다 크면 -1을 반환했다.

4방향을 모두 탐색하면서 기울였을 때 각 구슬이 위치할 최종 위치를 구한다.
구슬은 벽에 위치할 수 없으므로 벽에 위치할 경우 한 칸 전으로 이동하고 break 했고,
구슬이 구멍에 위치할 경우 바로 break했다.

파란 구슬이 구멍에 위치할 경우는 실패한 경우이므로 continue하여 다른 방향을 고려한 경우로 넘어간다.

빨간 구슬이 구멍에 위치할 경우에는 현재 동작 횟수를 반환한다. (앞서 조건에 파란 구슬이 동시에 빠진 경우는 제거된다.)

빨간 구슬과 파란 구슬이 같은 칸에 위치할 수 없으므로 더 많이 이동한 것이(더 뒤에 있던 구슬) 한 칸 전으로 간다.

이렇게 이동한 두 구슬이 전에 방문했던 상황이 아니라면, 방문처리하고, 큐에 move를 +1하여 넣는다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import deque
n, m = map(int, input().split())
board = [
    list(input().rstrip())
    for _ in range(n)
]
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)] # red, blue visited
dxs = [0,1,0,-1]
dys = [1,0,-1,0]

rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
    for j in range(m):
        if board[i][j] == 'R':
            rx, ry = i, j
        if board[i][j] == 'B':
            bx, by = i, j

def bfs(rx, ry, bx, by):
    visited[rx][ry][bx][by] = True
    q = deque([(rx, ry, bx, by, 1)])
    while q:
        rx, ry, bx, by, move = q.popleft()
        if move > 10:
            return -1
        for dx, dy in zip(dxs, dys):
            nrx, nry = rx, ry
            while True:
                nrx, nry = nrx + dx, nry + dy
                if board[nrx][nry] == '#':
                    nrx, nry = nrx - dx, nry - dy
                    break
                if board[nrx][nry] == 'O':
                    break
            nbx, nby = bx, by
            while True:
                nbx, nby = nbx + dx, nby + dy
                if board[nbx][nby] == '#':
                    nbx, nby = nbx - dx, nby - dy
                    break
                if board[nbx][nby] == 'O':
                    break
            if board[nbx][nby] == 'O':
                continue
            if board[nrx][nry] == 'O':
                return move
            if (nrx, nry) == (nbx, nby):
                if abs(nrx-rx)+abs(nry-ry) > abs(nbx-bx)+abs(nby-by):
                    nrx, nry = nrx - dx, nry - dy
                else:
                    nbx, nby = nbx - dx, nby - dy
            if not visited[nrx][nry][nbx][nby]:
                visited[nrx][nry][nbx][nby] = True
                q.append((nrx, nry, nbx, nby, move+1))
    return -1

print(bfs(rx, ry, bx, by))

끝으로..

매우 오래걸린 문제였다. 처음에 단순히 구현으로만 접근해서 알고리즘을 사용할 생각을 못했다.
아직 부족하다는 것을 많이 느끼는 문제였다.