알고리즘

[백준] 15644 - 구슬 탈출 3

2026년 01월 15일

#Python 3 #알고리즘 #그래프 이론 #그래프 탐색 #너비 우선 탐색 #격자 그래프 #구현 #시뮬레이션 #백준 #역추적

[Gold I] 구슬 탈출 3 - 15644

문제 링크

성능 요약

메모리: 35084 KB, 시간: 68 ms

분류

구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색, 격자 그래프, 역추적

문제 설명

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지, 또 어떻게 기울여야 하는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

첫째 줄에 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지, 둘째 줄에 어떻게 기울여야 하는지 순서대로 출력한다. 왼쪽으로 기울이기는 'L', 오른쪽으로 기울이기는 'R', 위로 기울이기는 'U', 아래로 기울이기는 'D'로 출력하며, 공백없이 한 줄에 모두 출력한다. 가능한 방법이 여러 가지면, 아무거나 출력한다.

만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

문제 풀이

문제 분석

이 문제는 "구슬 탈출" 게임을 시뮬레이션하여 빨간 구슬을 구멍에 빠뜨리는 최소 이동 횟수와 그 경로를 찾는 문제입니다. 중요한 규칙들은 다음과 같습니다.

목표: 빨간 구슬(R)을 구멍(O)을 통해 빼내야 합니다.
실패 조건: 파란 구슬(B)이 구멍에 들어가면 안 됩니다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠지는 것도 실패입니다.
동작: 상하좌우 네 방향으로 보드를 기울일 수 있습니다. 구슬들은 더 이상 움직이지 않을 때까지 동시에 이동합니다.
구슬 충돌: 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없습니다. 두 구슬이 부딪히면 멈춥니다.
제한: 최대 10번의 이동 내에 성공해야 합니다. 보드 크기는 최대 10x10입니다.
입력: 보드 크기 N, M과 보드 상태를 나타내는 문자열들 (.: 빈 칸, #: 벽, O: 구멍, R: 빨간 구슬, B: 파란 구슬).
출력: 첫째 줄에 최소 이동 횟수, 둘째 줄에 이동 경로(L, R, U, D 문자열). 10번 내에 성공하지 못하면 -1을 출력합니다.

접근 방법

문제에서 "최소 몇 번 만에"라는 조건을 요구하므로, 최단 경로를 찾는 데 가장 적합한 너비 우선 탐색 (BFS) 알고리즘을 사용합니다.

상태 정의: BFS는 각 단계에서 현재 상태로부터 도달할 수 있는 모든 다음 상태를 탐색합니다. 이 문제에서의 "상태"는 **(빨간 구슬의 현재 위치, 파란 구슬의 현재 위치, 현재까지의 이동 횟수, 현재까지의 이동 경로)**로 정의할 수 있습니다.
구슬의 동시 이동 시뮬레이션: 보드를 기울였을 때 두 구슬이 동시에 이동하고, 서로 부딪히면 멈추는 상황을 정확하게 시뮬레이션하는 것이 중요합니다. 이 코드에서는 빨간 구슬에 우선순위를 부여하여 충돌 시 처리하는 방식을 사용합니다.
방문 여부 확인: 같은 (빨간 구슬 위치, 파란 구슬 위치) 조합을 다시 탐색하는 것을 방지하기 위해 visited 집합을 사용하여 이미 방문한 상태를 기록합니다. 이는 불필요한 중복 계산을 줄이고 무한 루프를 방지합니다.

구현 설명

1. 초기 설정 및 BFS 큐 초기화

N, M을 입력받고 보드 graph를 저장합니다.
graph를 탐색하여 빨간 구슬(R)과 파란 구슬(B)의 초기 위치를 찾아 red와 blue 변수에 저장합니다. 구슬이 있던 자리는 빈 칸(.)으로 변경하여, graph는 움직이지 않는 장애물만 표현하도록 합니다.
collections.deque를 사용하여 BFS 큐 stack을 초기화하고, 초기 상태 (red, blue, 0, "") (빨간 구슬 위치, 파란 구슬 위치, 이동 횟수 0, 빈 경로)를 추가합니다.
visited 집합을 초기화하고, 초기 구슬 위치 조합((red[0], red[1], blue[0], blue[1]))을 추가하여 중복 탐색을 방지합니다.
네 가지 방향(L, R, U, D)에 대한 좌표 변화량을 dirs 딕셔너리에 정의합니다.

2. `move_dir` 함수: 특정 방향으로 구슬 이동 시뮬레이션

이 함수는 현재 빨간 구슬 r과 파란 구슬 b의 위치, 현재 이동 횟수 cnt, 경로 ops, 그리고 기울일 방향 d를 인자로 받습니다.
빨간 구슬 이동: 먼저 빨간 구슬(rx, ry)을 d 방향으로 벽('#')이나 구멍('O')을 만날 때까지 이동시킵니다.
- 이동 중 구멍에 빠지면 redhole = True로 설정하고 구멍 위치를 new_red로 저장합니다.
- 벽을 만나면 벽 바로 앞 칸에서 멈춥니다.
- 만약 빨간 구슬이 이동 중 파란 구슬의 초기 위치 (bx, by)에 닿았다면 withBlue = True로 표시합니다.
withBlue 상황 처리: 만약 withBlue가 True이면 (빨간 구슬이 파란 구슬의 초기 위치를 침범했으면):
- bluehole = True로 설정하여 파란 구슬도 구멍에 빠진 것으로 간주합니다.
- 만약 redhole도 True이면 두 구슬이 동시에 구멍에 빠진 것이므로 None을 반환하여 실패 처리하고 함수를 종료합니다.
- new_blue를 new_red와 동일하게 설정하고, new_red를 한 칸 뒤로 물립니다. 이는 빨간 구슬이 파란 구슬에 의해 밀려났다는 것을 의미합니다.
- 이후 새로운 상태를 visited에 추가하고 큐에 넣은 뒤 함수를 종료합니다.
파란 구슬 이동 (만약 withBlue가 아니었다면): 파란 구슬(bx, by)을 d 방향으로 벽이나 구멍을 만날 때까지 이동시킵니다.
- 이동 중 구멍에 빠지면 bluehole = True로 설정합니다.
- 벽을 만나면 벽 바로 앞 칸에서 멈춥니다.
최종 결과 판정 및 충돌 보정:
- redhole은 True인데 bluehole이 False이면 빨간 구슬만 성공적으로 빠진 경우이므로, "SUCCESS"와 함께 횟수, 경로를 반환하여 성공을 알립니다.
- bluehole이 True이면 파란 구슬이 구멍에 빠졌으므로 None을 반환하여 실패 처리합니다.
- 성공도 실패도 아니며, 두 구슬이 최종적으로 같은 위치(new_red == new_blue)에 있다면, 파란 구슬을 기울이는 방향의 반대편으로 한 칸 물립니다. (이 코드는 빨간 구슬이 파란 구슬보다 우선순위가 높다고 가정합니다.)
새로운 상태 (new_red, new_blue)가 visited에 없으면 추가하고 BFS 큐 stack에 넣습니다.

3. BFS 실행 및 결과 출력

while stack: 루프를 돌면서 BFS를 진행합니다.
큐에서 (r, b, cnt, ops)를 꺼냅니다.
현재 이동 횟수 cnt가 10 이상이면 문제 조건에 따라 더 이상 탐색하지 않고 break합니다.
네 가지 방향('L', 'R', 'U', 'D') 각각에 대해 move_dir 함수를 호출하여 다음 상태를 탐색합니다.
move_dir 함수가 "SUCCESS"를 반환하면, 그 횟수와 경로를 출력하고 프로그램을 종료합니다.
BFS가 모든 가능한 상태를 탐색했음에도 (또는 10번 이상 움직여서) 성공하지 못하면, 최종적으로 -1을 출력합니다.

⏱복잡도 분석

시간 복잡도:
- 보드 크기 N * M은 최대 10 * 10 = 100입니다.
- 두 구슬의 위치 조합은 (N*M) * (N*M) 가지이므로 최대 100 * 100 = 10000가지 상태가 있습니다.
- BFS는 각 상태를 최대 한 번만 방문하며, 각 상태에서 4가지 방향으로 이동을 시도합니다.
- move_dir 함수 내에서 구슬이 이동하는 데는 최대 N 또는 M번의 연산(최대 10번)이 필요합니다.
- BFS의 최대 깊이가 10으로 제한되어 있습니다.
- 따라서, 최악의 경우 시간 복잡도는 O((N*M)^2 * 4 * (N+M)) 정도로 근사할 수 있습니다. 실제 연산 수는 10000 * 4 * 20 = 8 * 10^5 정도이며, 여기에 최대 깊이 10을 곱하더라도 8 * 10^6 정도로, 주어진 시간 제한(1초) 내에 충분히 해결 가능합니다.
공간 복잡도:
- visited 집합은 최대 (N*M)^2개의 상태를 저장할 수 있습니다. 각 상태는 빨간 구슬과 파란 구슬의 4개 좌표(rx, ry, bx, by)로 구성됩니다.
- BFS 큐 stack도 최악의 경우 (N*M)^2개의 상태를 저장할 수 있으며, 각 상태는 구슬 위치, 카운트, 최대 길이 10의 경로 문자열을 포함합니다.
- 따라서 공간 복잡도는 O((N*M)^2 * (경로_최대_길이)) 입니다. (10*10)^2 * 10 = 10000 * 10 = 10^5 정도의 정수 및 문자열 데이터를 저장하며, 이는 주어진 메모리 제한(256MB) 내에서 충분히 처리 가능합니다.

핵심 포인트

BFS를 활용한 최단 경로 탐색: 문제의 목표가 최소 이동 횟수를 찾는 것이므로, 시작 상태에서 목표 상태까지의 최단 경로를 보장하는 BFS가 핵심 알고리즘입니다. 각 상태를 구슬들의 위치, 이동 횟수, 경로로 정의하여 큐에 저장하고 탐색합니다.
구슬 동시 이동 및 충돌 처리: 두 구슬이 동시에 움직이며 벽이나 구멍을 만날 때까지 이동합니다. 이 코드에서는 빨간 구슬에 우선순위를 부여하여, 만약 두 구슬이 같은 칸에 최종적으로 도달한다면 파란 구슬을 한 칸 뒤로 물리는 방식으로 충돌을 처리합니다. 또한, 파란 구슬이 구멍에 빠지는 경우는 무조건 실패로 간주합니다.
상태 중복 방지를 위한 visited 집합: (빨간 구슬 위치, 파란 구슬 위치)의 조합으로 정의되는 각 상태를 visited 집합에 기록하여, 이미 탐색한 상태는 다시 탐색하지 않도록 함으로써 불필요한 계산을 줄이고 탐색 효율성을 높입니다.

풀이 코드

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().strip()) for _ in range(n)]

for i in range(n):
    for j in range(m):
        if graph[i][j] == "R":
            graph[i][j] = "."
            red = (i, j)
        if graph[i][j] == "B":
            graph[i][j] = "."
            blue = (i, j)

redhole = False
bluehole = False

stack = deque([(red, blue, 0, "")])
visited = set()
visited.add((red[0], red[1], blue[0], blue[1]))
cnt = 0

dirs = {
    "L": (0, -1),
    "R": (0, 1),
    "U": (-1, 0),
    "D": (1, 0),
}

def move_dir(r, b, cnt, ops, d):
    rx, ry = r
    bx, by = b
    dx, dy = dirs[d]

    redhole = False
    bluehole = False
    withBlue = False

    while True:
        if rx == bx and ry == by:
            withBlue = True

        cur = graph[rx][ry]
        if cur == ".":
            rx += dx
            ry += dy
        elif cur == "O":
            redhole = True
            new_red = (rx, ry)
            break
        elif cur == "#":
            new_red = (rx - dx, ry - dy)
            break

    if withBlue:
        bluehole = True
        if redhole:
            return None

        new_blue = new_red
        new_red = (new_red[0] - dx, new_red[1] - dy)

    else:
        while True:
            cur = graph[bx][by]
            if cur == ".":
                bx += dx
                by += dy
            elif cur == "O":
                bluehole = True
                break
            elif cur == "#":
                new_blue = (bx - dx, by - dy)
                break

        if redhole and not bluehole:
            return "SUCCESS", cnt + 1, ops + d

        if bluehole:
            return None

        if new_red == new_blue:
            new_blue = (new_blue[0] - dx, new_blue[1] - dy)

    moved = (new_red[0], new_red[1], new_blue[0], new_blue[1])
    if moved not in visited:
        visited.add(moved)
        stack.append((new_red, new_blue, cnt + 1, ops + d))

    return None

while stack:
    r, b, cnt, ops = stack.popleft()
    if cnt >= 10:
        break

    for d in ["L", "R", "U", "D"]:
        result = move_dir(r, b, cnt, ops, d)
        if result and result[0] == "SUCCESS":
            print(result[1])
            print(result[2])
            sys.exit()

print(-1)

댓글을 불러오는 중...