풀이
간만에 그래프탐색 문제이다.
두 개의 구슬이 위치한 보드를 기울여서 빨간구슬만 10번안에 탈출시키면 성공하는 게임이다.
처음엔 각 구슬에 대하여 BFS 를 실행하면 되는 줄 알았는데 방문처리가 문제여서 다른분들의 풀이를 참고하면서 풀었다.
타 BFS 문제들과의 차이점이 있었는데,
-
이동한 방향이 벽에 닿을 때 까지 혹은 도착점에 도착할 때 까지 같은 방향으로 쭉 이동해야 한다는 조건.
-
두 구슬이 함께 움직인다는 조건.
위 두가지 조건을 모두 충족시키면서 문제를 풀어야했다.
move() 함수를 새로 정의하면서 각 방향마다 벽에 닿거나 도착점에 도착할 경우까지 이동 후 좌표를 리턴해주는 식으로 구현하였고 이 때 두 개의 구슬이 함께 움직이기 때문에 겹칠 가능성을 고려하여 얼마나 이동했는지를 판단할 c 값을 추가로 리턴해주었다.
이동 후 파란 구슬은 도착점에 도착하지 않고 빨간 구슬만 도착점에 도착했다면 정답이기 때문에 현재까지 몇 번 기울였는지 출력하고 종료하면된다.
만약 두 개의 구슬이 겹쳤을 경우 더 많이 이동한 구슬이 뒤쪽에 위치해야하기 때문에 해당 구슬의 좌표를 한 칸 밀어서 배치해준다.
만약 정답이 나오지 않았으며 두 구슬의 위치가 방문하지 않았던 경우라면 해당 값들을 큐에 다시 삽입해준 뒤 위 과정을 반복한다.
소스코드
# 구슬 탈출 2
from collections import deque
import sys
input = sys.stdin.readline
def move(x, y, dx, dy):
c = 0
while board[x + dx][y + dy] != "#" and board[x][y] != "O": # 벽을 만나거나 도착점에 도착할 때 까지
x += dx
y += dy
c += 1
return x, y, c
def bfs():
while q:
rx, ry, bx, by, d = q.popleft()
if d > 10: # 10번 이상 기울였을 경우 실패
break
for i in range(4):
nrx, nry, rc = move(rx, ry, dx[i], dy[i])
nbx, nby, bc = move(bx, by, dx[i], dy[i])
if board[nbx][nby] != "O": # 파란구슬이 도착점에 위치하지 않고
if board[nrx][nry] == "O": # 빨간구슬만 도착점에 위치했을 때
print(d) # 기울인 횟수 출력 후 종료
return
if nrx == nbx and nry == nby: # 파란구슬과 빨간구슬이 겹쳤을 경우
if rc > bc: # 빨간구슬이 더 많이 이동했을 경우 한 칸 뒤로
nrx -= dx[i]
nry -= dy[i]
else: # 파란구슬이 더 많이 이동했을 경우 한 칸 뒤로
nbx -= dx[i]
nby -= dy[i]
if not visited[nrx][nry][nbx][nby]: # 이동 후 빨간구슬과 파란구슬의 위치가 아직 한 번도 위치해보지않았던 위치라면
visited[nrx][nry][nbx][nby] = True # 방문처리 이후 큐에 삽입
q.append([nrx, nry, nbx, nby, d+1])
print(-1)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n, m = map(int, input().split())
board = []
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)] # 빨간구슬과 파란구슬의 좌표에 대한 방문좌표 선언
for i in range(n):
line = list(input().rstrip())
board.append(line)
for j in range(m):
if line[j] == "B":
bx, by = i, j
elif line[j] == "R":
rx, ry = i, j
q = deque()
q.append([rx, ry, bx, by, 1])
visited[rx][ry][bx][by] = True
bfs()