문제
BOJ 13460: 구슬 탈출 2 https://www.acmicpc.net/problem/13460
풀이
조건
- 보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다.
- 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다.
- 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이다.
- 빨간 구슬과 파란 구슬은 각각 하나씩 들어가 있다.
- 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다.
- 이때, 파란 구슬이 구멍에 들어가면 안 된다.
- 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작으로 공을 굴려서 빼낸다.
- 각각의 동작에서 공은 동시에 움직인다.
- 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다.
- 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.
- 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.
- 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.
- 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
- 입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.
풀이 순서
- 빨간 구슬과 파란 구슬의 초기 위치를 저장한다.
- BFS를 사용해 해결한다.
- 4차원 배열을 사용해 빨간 구슬과 파란 구슬이 위치했던 상황을 기록한다.
- 4 방향으로 두 구슬을 굴린다.
- 두 구슬이 굴려진 뒤의 상황으로 결과를 확인한다.
코드
Python
import sys
from collections import deque
N, M = map(int, sys.stdin.readline().rstrip().split())
board = [list(sys.stdin.readline().rstrip()) for _ in range(N)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
# 빨간 구슬, 파란 구슬이 위치한 상태를 기록하기 위한 4차원 배열
visited = [[[[False for _ in range(M)] for _ in range(N)] for _ in range(M)] for _ in range(N)]
# 입력받은 방향으로 공을 끝까지 굴리는 함수
def roll(x, y, direction):
cnt = 0
while True:
nx = x + dx[direction]
ny = y + dy[direction]
# 다음 위치가 벽이거나 현재 위치가 구멍('O')이면 종료
if board[nx][ny] == '#' or board[x][y] == 'O':
break
x = nx
y = ny
cnt += 1
# 마지막 위치와 굴러간 횟수 반환
return x, y, cnt
# BFS를 사용해 빨간 구슬과 파란 구슬을 동시에 굴리며 답 찾기
def bfs(ra, rb, ba, bb):
que = deque()
que.append([ra, rb, ba, bb, 1])
while que:
rx, ry, bx, by, move_cnt = que.popleft()
# 현재 상황 기록
visited[rx][ry][bx][by] = True
# 판을 기울인 회수가 10 넘어가면 종료
if move_cnt > 10:
return -1
# 다음 방향으로 굴린 결과 확인
for t in range(4):
# 빨간 구슬 결과
nrx, nry, rcnt = roll(rx, ry, t)
# 파란 구슬 결과
nbx, nby, bcnt = roll(bx, by, t)
# 파란 구슬이 구멍('O')에 없을 때 (파란 구슬이 구멍('O')에 있는 상황은 걸러냄)
if board[nbx][nby] != 'O':
# 빨간 구슬이 구멍('O')에 도달하면 종료
if board[nrx][nry] == 'O':
return move_cnt
# 두 공이 겹치면 앞뒤 구분해서 재배치
if nrx == nbx and nry == nby:
# 구슬이 더 많이 구름 -> 더 뒤쪽이었다는 뜻
if rcnt > bcnt:
nrx -= dx[t]
nry -= dy[t]
else:
nbx -= dx[t]
nby -= dy[t]
# 굴린 결과가 아직 겪지 않은 상황이면
if not visited[nrx][nry][nbx][nby]:
# 겪은 상황이라고 체크
visited[nrx][nry][nbx][nby] = True
# 큐에 넣기
que.append([nrx, nry, nbx, nby, move_cnt + 1])
# 게임을 종료할 수 없으면 -1 반환하고 종료
return -1
a, b, c, d = 0, 0, 0, 0
for i in range(N):
for j in range(M):
if board[i][j] == 'R':
a = i
b = j
if board[i][j] == 'B':
c = i
d = j
result = bfs(a, b, c, d)
print(result)정리
- 처음에는 백트래킹을 사용해 판을 기울이는 조합을 구하고 구슬들을 굴려보며 답을 구하려고 했다.
- BFS를 사용해 판을 기울이는 횟수의 최소값을 구할 수 있다는 것을 알았다.
