[백준] 12460번 구슬 탈출 2 (Python)

백준 12460 구슬 탈출 2

BFS를 활용한 구현 문제였다. 구현 문제를 해결할 때 케이스 분류를 정확하게 해야 한다는 것을 다시 깨닫게 되는 문제였다. 구글링을 통해서 찾아본 이 문제의 솔루션은 생각보다 단순했다. 함수를 적극적으로 활용하여 코드의 길이를 줄이는 연습 또한 필요할 것 같다. 나는 이 문제를 풀면서 3가지 실수를 했다.

1. 케이스 분류를 제대로 하지 못했다.
2. grid에서 탐색을 할 때, grid[y][x]가 아닌 grid[x][y]로 수식을 적어 실수했다.
3. x 값이 고정이고 y값을 기준으로 탐색해야 하는 경우 in 문법을 쓰기 위해서는 리스트를 새로 선언해야 했다.
   ex) True not in [isWall[i][hx] for i in range(hy, by + 1)]

구현을 위해서 나누 케이스는 이와 같다.

1. 파란 공의 한 좌표와 구멍의 한 좌표가 같고 사이에 벽이 없는 경우
2. 빨간 공의 한 좌표와 구멍의 한 좌표가 같고 사이에 벽이 없는 경우
3. 빨간 공과 파란 공이 같은 축에 존재하는 경우, 이동해야 하는 방향 공부터 이동
4. 빨간 공과 파란 공이 다른 축에 존재하는 경우, 각자 이동

import sys
from collections import deque

def move(ry, rx, by, bx, p):
    if p == 0:
        return up(ry, rx, by, bx)
    if p == 1:
        return right(ry, rx, by, bx)
    if p == 2:
        return down(ry, rx, by, bx)
    if p == 3:
        return left(ry, rx, by, bx)
    
def up(ry, rx, by, bx):
    if hx == bx and hy < by and True not in [isWall[i][hx] for i in range(hy, by + 1)]:
            return [-2, -2, -2, -2]
    if hx == rx and hy < ry and True not in [isWall[i][hx] for i in range(hy, ry + 1)]:
            return [-1, -1, -1, -1]
    if rx == bx:
        if by < ry:
            while not isWall[by - 1][bx]:
                by -= 1
            while not isWall[ry - 1][rx] and ry - 1 != by:
                ry -= 1
        else:
            while not isWall[ry - 1][rx]:
                ry -= 1
            while not isWall[by - 1][bx] and by - 1 != ry:
                by -= 1
    else:
        while not isWall[by - 1][bx]:
                by -= 1
        while not isWall[ry - 1][rx]:
                ry -= 1
    return [ry, rx, by, bx]
    
def down(ry, rx, by, bx):
    if hx == bx and hy > by and True not in [isWall[i][hx] for i in range(by, hy + 1)]:
        return [-2, -2, -2, -2]
    if hx == rx and hy > ry and True not in [isWall[i][hx] for i in range(ry, hy + 1)]:
        return [-1, -1, -1, -1]
    if rx == bx:
        if by > ry:
            while not isWall[by + 1][bx]:
                by += 1
            while not isWall[ry + 1][rx] and ry + 1 != by:
                ry += 1
        else:
            while not isWall[ry + 1][rx]:
                ry += 1
            while not isWall[by + 1][bx] and by + 1 != ry:
                by += 1
    else:
        while not isWall[by + 1][bx]:
                by += 1
        while not isWall[ry + 1][rx]:
                ry += 1
    return [ry, rx, by, bx]
    
def right(ry, rx, by, bx):
    if hy == by and hx > bx and True not in isWall[hy][bx: hx + 1]:
        return [-2, -2, -2, -2]
    if hy == ry and hx > rx and True not in isWall[hy][rx: hx + 1]:
            return [-1, -1, -1, -1]
    if ry == by:
        if bx > rx:
            while not isWall[by][bx + 1]:
                bx += 1
            while not isWall[ry][rx + 1] and rx + 1 != bx:
                rx += 1
        else:
            while not isWall[ry][rx + 1]:
                rx += 1
            while not isWall[by][bx + 1] and bx + 1 != rx:
                bx += 1
    else:
        while not isWall[by][bx + 1]:
            bx += 1
        while not isWall[ry][rx + 1]:
            rx += 1
    return [ry, rx, by, bx]

def left(ry, rx, by, bx):
    if hy == by and hx < bx and True not in isWall[hy][hx: bx + 1]:
            return [-2, -2, -2, -2]
    if hy == ry and hx < rx and True not in isWall[hy][hx: rx + 1]:
            return [-1, -1, -1, -1]
    if ry == by:
        if bx < rx:
            while not isWall[by][bx - 1]:
                bx -= 1
            while not isWall[ry][rx - 1] and rx - 1 != bx:
                rx -= 1
        else:
            while not isWall[ry][rx - 1]:
                rx -= 1
            while not isWall[by][bx - 1] and bx - 1 != rx:
                bx -= 1
    else:
        while not isWall[by][bx - 1]:
            bx -= 1
        while not isWall[ry][rx - 1]:
            rx -= 1
    return [ry, rx, by, bx]

input = sys.stdin.readline
n, m = map(int, input().split())
by, ry, hy, bx, rx, hx = 0, 0, 0, 0, 0, 0
isWall = [[False for _ in range(m)] for __ in range(n)]
isVisit = set()
q = deque()
for y in range(n):
    tmp = input().strip()
    for x in range(m):
        if tmp[x] == "B":
            by , bx = y, x
        elif tmp[x] == "R":
            ry , rx = y, x
        elif tmp[x] == "O":
            hy , hx = y, x
        elif tmp[x] == "#":
            isWall[y][x] = True
q.append([ry, rx, by, bx, 0])
isVisit.add((ry, rx, by, bx))

while q:
    ry, rx, by, bx, cnt = q.popleft()
    for i in range(4):
        tmpry, tmprx, tmpby, tmpbx = move(ry, rx, by, bx, i)
        if tmpry == -1:
            print(cnt + 1)
            exit(0)
        elif tmpry != -2 and cnt < 9:
            if (tmpry, tmprx, tmpby, tmpbx) not in isVisit:
                isVisit.add((tmpry, tmprx, tmpby, tmpbx))
                q.append([tmpry, tmprx, tmpby, tmpbx, cnt + 1])
print(-1)