메모리: 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)이 구멍에 들어가면 안 됩니다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠지는 것도 실패입니다.N, M과 보드 상태를 나타내는 문자열들 (.: 빈 칸, #: 벽, O: 구멍, R: 빨간 구슬, B: 파란 구슬).L, R, U, D 문자열). 10번 내에 성공하지 못하면 -1을 출력합니다.문제에서 "최소 몇 번 만에"라는 조건을 요구하므로, 최단 경로를 찾는 데 가장 적합한 너비 우선 탐색 (BFS) 알고리즘을 사용합니다.
visited 집합을 사용하여 이미 방문한 상태를 기록합니다. 이는 불필요한 중복 계산을 줄이고 무한 루프를 방지합니다.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 딕셔너리에 정의합니다.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에 넣습니다.while stack: 루프를 돌면서 BFS를 진행합니다.(r, b, cnt, ops)를 꺼냅니다.cnt가 10 이상이면 문제 조건에 따라 더 이상 탐색하지 않고 break합니다.move_dir 함수를 호출하여 다음 상태를 탐색합니다.move_dir 함수가 "SUCCESS"를 반환하면, 그 횟수와 경로를 출력하고 프로그램을 종료합니다.-1을 출력합니다.시간 복잡도:
N * M은 최대 10 * 10 = 100입니다.(N*M) * (N*M) 가지이므로 최대 100 * 100 = 10000가지 상태가 있습니다.move_dir 함수 내에서 구슬이 이동하는 데는 최대 N 또는 M번의 연산(최대 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)로 구성됩니다.stack도 최악의 경우 (N*M)^2개의 상태를 저장할 수 있으며, 각 상태는 구슬 위치, 카운트, 최대 길이 10의 경로 문자열을 포함합니다.O((N*M)^2 * (경로_최대_길이)) 입니다. (10*10)^2 * 10 = 10000 * 10 = 10^5 정도의 정수 및 문자열 데이터를 저장하며, 이는 주어진 메모리 제한(256MB) 내에서 충분히 처리 가능합니다.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)