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

www.acmicpc.net/problem/13460

import sys
import copy
input = sys.stdin.readline

TOP, RIGHT, BOTTOM, LEFT = 0, 1, 2, 3
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def bfs():
    global curMap, curRedPos, curBluePos

    todo = [[map, redPos, bluePos, 1]]
    # 2개의 구슬의 위치를 기록하여 중복을 허용하지 않도록 함
    ballRecords = [[redPos, bluePos]]

    while todo:
        curOriginalMap, curOriginalRedPos, curOriginalBluePos, curCount = todo.pop(
            0)
        if curCount >= 11:
            return -1

        for j in range(4):
            # curMap, curRedPos, curBluePos를 새로 만들면, 하위 함수들은 이 세 변수들을 수정함
            curMap = copy.deepcopy(curOriginalMap)
            curRedPos = copy.deepcopy(curOriginalRedPos)
            curBluePos = copy.deepcopy(curOriginalBluePos)

            # j에 따라 맵 기울이기... 이 때 curMap, curRedPos, curBluePos 모두 변함
            tiltBoard(j)

            # [-1, -1]의 의미는 O를 만나 떨어졌다는 것임
            if curBluePos == [-1, -1]:
                continue
            elif curRedPos == [-1, -1]:
                return curCount  # bfs이므로 바로 return 함
            else:
                # curRedPos, curBluePos의 값은 중복되면 안 됨
                if [curRedPos, curBluePos] in ballRecords:
                    continue

                # [변화된 curMap, curRedPos, curBluePos, 그리고 이동횟수+1]를
                todo.append([curMap, curRedPos, curBluePos, curCount+1])
                ballRecords.append([curRedPos, curBluePos])

    return -1


def tiltBoard(direction):
    global curMap, curRedPos, curBluePos

    # Red와 Blue 두 개에 대해서 tiltAndGetCollapsed를 수행해야하는데 순서를 정해줌
    # 순서 정하는 이유: [. R . B]에서 왼쪽으로 기울인다고 하자. B, R 순서로 기울이면 [R . B .]가 됨
    todo = [curRedPos, curBluePos]
    if direction == TOP:
        if curRedPos[0] > curBluePos[0]:
            todo = [curBluePos, curRedPos]
    elif direction == RIGHT:
        if curRedPos[1] < curBluePos[1]:
            todo = [curBluePos, curRedPos]
    elif direction == BOTTOM:
        if curRedPos[0] < curBluePos[0]:
            todo = [curBluePos, curRedPos]
    elif direction == LEFT:
        if curRedPos[1] > curBluePos[1]:
            todo = [curBluePos, curRedPos]

    # 정해진 순서에 따라서 각 구슬을 기울여줌
    for curPos in todo:
        isR = curPos == curRedPos

        if(tiltAndGetCollapsed(direction, curPos) == 'O'):
            curMap[curRedPos[0]][curRedPos[1]] = '.'

            # [-1, -1] 의미: 구슬이 구멍으로 떨어짐
            if isR:
                curRedPos = [-1, -1]
            else:
                curBluePos = [-1, -1]


def tiltAndGetCollapsed(direction, pos):
    curPos = [pos[0], pos[1]]
    while 0 <= curPos[0] <= N-1 and 0 <= curPos[1] <= M-1:
        curPos[0] += dx[direction]
        curPos[1] += dy[direction]

        if curMap[curPos[0]][curPos[1]] != '.':
            moveBall(pos, [curPos[0]-dx[direction], curPos[1]-dy[direction]])
            return curMap[curPos[0]][curPos[1]]


def moveBall(prevPos, nextPos):
    if prevPos == nextPos:
        return

    global curMap, curRedPos, curBluePos

    if prevPos == curRedPos:
        curRedPos = nextPos
    elif prevPos == curBluePos:
        curBluePos = nextPos

    curMap[nextPos[0]][nextPos[1]] = curMap[prevPos[0]][prevPos[1]]
    curMap[prevPos[0]][prevPos[1]] = '.'


N, M = map(int, input().split())
map = []
curMap = None
curRedPos = [-1, -1]
curBluePos = [-1, -1]

for i in range(N):
    curInput = input().rstrip()
    curLine = []
    for j in range(M):
        c = curInput[j]
        if c == 'R':
            redPos = [i, j]
        elif c == 'B':
            bluePos = [i, j]
        curLine.append(c)
    map.append(curLine)

print(bfs())

코드가 워낙 방대해서 설명을 주석에 상세하게 달았다. 그래도 큰 틀 정도는 설명하겠다.

 

• todo-list를 통해 큐 형태로 bfs를 돌리는데, todo의 각 원소에는 [맵, 빨간 구슬 좌표, 파란 구슬 좌표, 이동횟수]가 저장된다.
  • 각 원소의 4개의 요소는 'curOriginal-'의 변수 4개에 저장된다.
  • for문으로 0~3(상, 우, 하, 좌)을 돌면서,
    • curMap, curRedPos, curBluePos를 'curOriginal-'로부터 깊은복사 한다.
    • tiltBoard()를 호출함으로써 curMap, curRedPos, curBluePos가, 특정 방향으로 기울였을 때의 값으로 변동된다.
    • 그렇게 변동된 값을 토대로, 파란 구슬이 떨어졌다면 유효하지 않은 것이므로 continue, 빨간 구슬이 떨어졌다면 이 문제의 목적이 달성된 것이므로 이동횟수를 리턴해준다.
    • 구슬이 떨어지지 않았다면, todo에 변동된 정보들을 추가하고, 구슬들의 위치를 ballRecords에 저장하여 중복을 불허한다. 이에 따라서, 정보를 추가하기 전에, ballRecords를 확인하여, 현재 변동된 구슬들의 위치가 이전에 있었는지 확인한다.

 

여담으로, 지엽적이고, 정보 저장이 그렇게 효율적인 것 같지 않았음에도 불구하고,

1. 이동이 10번으로 제한됨 2. 구슬의 위치를 통해 중복을 허용하지 않음

이라는 이유들로 인해 꽤 괜찮은 시간복잡도가 나왔다.