[BOJ 13459] 구슬 탈출(Python)

문제

구슬 탈출

---

문제 해설

이 문제는 BFS를 통해 푸는 문제이나, 구현을 하는 과정이 복잡하기 때문에 시뮬레이션으로도 분류를 했습니다.

요구하는 사항은 어렵지 않습니다. 공을 사방으로 굴려 10번 안에 빨간공이 골인지점에 도착하면 됩니다. 하지만 파란공이 같이들어오면 안된다는 점이 중요합니다.

1. 공의 위치를 파악합니다. 공을 위, 오른쪽, 아래, 왼쪽으로 끝까지 굴리고 끝나는 지점이 다른 공이 있거나 벽이 있거나 골인지점을 통과했을 때이기 때문에 각 방향마다 어떤 공을 먼저 도착시켜야 하는지 판단해야 합니다. 왼쪽으로 굴린다면 y좌표가 더 작은 공을 먼저 굴립니다.

2. 공을 굴립니다. 만약 두 공을 굴렸는데 굴려서 도착한지점이 전과 똑같다면 큐에 넣지 않습니다.

3. 큐에서 두 공의 좌표를 빼내어 1번으로 돌아갑니다.

저의 코드에서는 graph에서 R과 B를 제거한 뒤 좌표로만 계산을 했습니다. 왜냐하면 R과 B를 graph에서 다루게 된다면 copy 라이브러리로 계속 2차원 리스트를 생성하여 비교하는 수밖에 없는데, 메모리 낭비가 어마어마할 것 같아 방식을 바꾸게 되었습니다.

---

풀이 코드

# 3:10
import sys
from collections import deque

input = sys.stdin.readline
dx = -1, 0, 1, 0
dy = 0, 1, 0, -1
n, m = map(int, input().split())
graph = [list(map(str, input().rstrip())) for _ in range(n)]

q = deque()
rx = ry = bx = by = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] == "R":
            rx, ry = i, j
            graph[i][j] = "."
        elif graph[i][j] == "B":
            bx, by = i, j
            graph[i][j] = "."


def move(x, y, anox, anoy, dir):
    # 공의 좌표, 다른 공의 좌표, 방향을 인자로 받는다.
    # 벽을 만나거나 다른 공을 만나면 종료한다.
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        # 골인 지점을 통과 시
        if graph[nx][ny] == "O":
            return (0, 0)
        if graph[nx][ny] == "#" or (nx == anox and ny == anoy):
            return (x, y)
        x, y = nx, ny


def who_first(rx, ry, bx, by, dir):
    # 어떤 공을 먼저 움직일지 결정
    if dir == 0:
        # 북쪽, x좌표가 낮은것을 선택
        return "R" if rx < bx else "B"
    elif dir == 1:
        return "R" if ry > by else "B"
    elif dir == 2:
        return "R" if rx > bx else "B"
    else:
        return "R" if ry < by else "B"


time = 0
q.append((rx, ry, bx, by))
while time < 10:
    size = len(q)
    for _ in range(size):
        rx, ry, bx, by = q.popleft()
        # 0:북 1:동 2:남 3:서
        for i in range(4):
            if who_first(rx, ry, bx, by, i) == "R":
                # 빨간 공 먼저 움직임
                nrx, nry = move(rx, ry, 0, 0, i)
                nbx, nby = move(bx, by, nrx, nry, i)
            else:
                nbx, nby = move(bx, by, 0, 0, i)
                nrx, nry = move(rx, ry, nbx, nby, i)
            # 파란 공이 일단 골인 지점에 들어가지만 않으면 bfs 계속 진행
            # 빨간 공만 골인지점에 통과 했을 때 종료
            if nbx != 0:
                if nrx == 0:
                    print(1)
                    exit()
                # 이동 한게 이동 전이랑 똑같으면 큐에 넣지 않음
                if not (rx == nrx and ry == nry and bx == nbx and by == nby):
                    q.append((nrx, nry, nbx, nby))
    time += 1
print(0)

---