[BOJ 13460] 구슬 탈출 2

 

13460번: 구슬 탈출 2

 

처음에 문제를 잘못 봐 구슬이 각각 하나씩 있는 줄 모르고 '이거 무조건 메모리 초과 뜰 거 같은데...' 하면서 2시간을 낭비하고 만 문제이다. (사실 문제를 제대로 본 다음에도 제대로 못 풀었다)

 

문제 해결을 위한 대략적인 아이디어는 다음과 같다.

• 보드의 상태를 직접 변경하는 것이 아닌, 보드를 확인하며 구슬의 좌표만을 변경하는 것이 핵심이다. 이를 위해 처음 구슬들의 좌표를 확인해서 저장한다. 
• 구슬을 움직일 때는 벽('#')과 구멍('O')를 모두 고려해서 움직여야 한다. 한 번에 옮기기보다 루프 내에서 다음 칸을 확인하며 한 칸씩 움직이도록 하는 것이 구현상 편해 그렇게 했다.
• move_marble 함수를 통해 움직이고 난 다음 두 구슬의 좌표가 같은 경우, 더 적게 움직인 구슬이 해당 좌표에 먼저 도달하게 되므로 더 많이 움직인 구슬의 경우 한 칸 되돌려준다.
• queue에는 두 구슬의 좌표와 함께 움직인 횟수가 담긴 tuple을 넣어, 움직인 횟수가 10 이상인 tuple이 나올 시 bfs 특성상 이 이후 모두 움직인 횟수가 10 이상인 tuple만 queue 내부에 있으므로 즉시 while loop를 종료한다.
• 중복된 좌표 방문을 피하기 위해 dictionary 자료형을 활용하였다.

from collections import deque
In = __import__('sys').stdin.readline
N, M = map(int, In().split())
board = [[' '] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
cur_coor = [0, 0, 0, 0, 0]
check = {}
for i in range(N):
    temp = In().rstrip()
    for j in range(M):
        board[i][j] = temp[j]
        if temp[j] == 'R':
            cur_coor[0] = i
            cur_coor[1] = j
            board[i][j] ='.'
        elif temp[j] == 'B':
            cur_coor[2] = i
            cur_coor[3] = j
            board[i][j] = '.'
queue = deque()
queue.append(tuple(cur_coor))


def move_marble(x, y, dir, board):
    while board[x+dir[0]][y+dir[1]] != '#' and board[x+dir[0]][y+dir[1]] != 'O':
        x += dir[0]
        y += dir[1]
    return (x, y)


def solution(queue, board, direction, check):
    while queue:

        temp = queue.popleft()

        # 종료 조건: bfs이니 10 이상이 한 번이라도 나오는 순간 종료.
        if temp[4] >= 10:
            break

        for x in range(4):
            new_Rx, new_Ry = move_marble(temp[0], temp[1], direction[x], board)
            new_Bx, new_By = move_marble(temp[2], temp[3], direction[x], board)
            time = temp[-1]

            # O에서 멈췄을 경우 파란 구슬도 멈추면 무시, 빨간 구슬만 멈춘 경우 bfs이므로 걸린 시간 return
            if board[new_Bx + direction[x][0]][new_By + direction[x][1]] == 'O': continue
            if board[new_Rx + direction[x][0]][new_Ry + direction[x][1]] == 'O':
                return (time+1)

            # 좌표가 같을 경우, 더 짧게 이동한 구슬이 먼저 도달한 것이니
            # 더 많이 이동한 구슬을 한 단계 거꾸로 보내준다.
            if new_Bx == new_Rx and new_By == new_Ry:
                dR = abs(temp[0] - new_Rx + temp[1] - new_Ry)
                dB = abs(temp[2] - new_Bx + temp[3] - new_By)
                if dR > dB:
                    new_Rx -= direction[x][0]
                    new_Ry -= direction[x][1]
                else:
                    new_Bx -= direction[x][0]
                    new_By -= direction[x][1]
            
            # dict를 visit 확인 용도로 사용한다.
            # (dict에서 in은 O(1) 시간)
            new_temp = (new_Rx, new_Ry, new_Bx, new_By)
            if not new_temp in check:
                check[new_temp] = 1
                queue.append((new_Rx, new_Ry, new_Bx, new_By, time+1))

    # bfs가 그냥 끝난 경우 들어갈 수 없는 경우이니 -1 return
    return -1


print(solution(queue, board, direction, check))