meatsby.github.io

BOJ 13460 - 구슬 탈출 2

5 min read

풀이

간만에 그래프탐색 문제이다.

두 개의 구슬이 위치한 보드를 기울여서 빨간구슬만 10번안에 탈출시키면 성공하는 게임이다.

처음엔 각 구슬에 대하여 BFS 를 실행하면 되는 줄 알았는데 방문처리가 문제여서 다른분들의 풀이를 참고하면서 풀었다.

타 BFS 문제들과의 차이점이 있었는데,

  1. 이동한 방향이 벽에 닿을 때 까지 혹은 도착점에 도착할 때 까지 같은 방향으로 쭉 이동해야 한다는 조건.

  2. 두 구슬이 함께 움직인다는 조건.

위 두가지 조건을 모두 충족시키면서 문제를 풀어야했다.

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()

References

Graph View