[백준 13460] 구슬 탈출 2

백준 13460

🔍 알고리즘 분류

• 구현
• 시뮬레이션
• bfs

💡 문제 풀이

1. goToEnd: 구슬이 한 방향으로 갈 수 있는 최대한으로 이동
2. 빨간 구슬과 파란 구슬에 대해 각각 goToEnd 진행
3. 파란 구슬이 O에 있을 경우 continue, 빨간 구슬이 O에 있을 경우 답 출력
4. 이동한 빨간 구슬과 파란 구슬의 위치가 겹쳐있을 경우: 더 많이 이동한 구슬 한 칸 뒤로
5. 두 구슬의 이동한 위치가 visited에 없을 경우 계속 탐색
   (visited 함수에는 빨간 구슬과 파란 구슬의 이동한 마지막 위치만 저장)

📄 코드

• Python

from collections import deque
import sys
input = sys.stdin.readline
 
n, m = map(int, input().split())
 
board = [list(input().rstrip()) for _ in range(n)]
visited = []
 
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
# 처음 구슬들 위치 반환
def getPos():
    rx, ry, bx, by = 0, 0, 0, 0
    for x in range(n):
        for y in range(m):
            if board[x][y] == "R":
                rx, ry = x, y
            if board[x][y] == "B":
                bx, by = x, y
    return rx, ry, bx, by
 
# 한 방향으로 갈 수 있는 끝까지 이동하는 함수
def goToEnd(x, y, dx, dy):
    cnt = 0
    # 이동하는 위치가 벽이아니고, 구멍에 들어가지 않을 동안 반복
    while board[x + dx][y + dy] != "#" and board[x][y] != "O":
        x += dx
        y += dy
        cnt +=1
    return x, y, cnt

# 너비 우선 탐색
def bfs():
    rx, ry, bx, by = getPos()
 
    q = deque()
    q.append((rx, ry, bx, by, 1))
    visited.append((rx, ry, bx, by))
 
    while q:
        rx, ry, bx, by, result = q.popleft()
 
        if result > 10:
            break
 
        for i in range(4):
            nrx, nry, rcnt = goToEnd(rx, ry, dx[i], dy[i])
            nbx, nby, bcnt = goToEnd(bx, by, dx[i], dy[i])

            # 파란 구슬이 구멍에 들어갈 경우
            if board[nbx][nby] == "O":
                continue
 
            # 빨간 구슬이 들어갈 경우 성공
            if board[nrx][nry] == "O":
                print(result)
                return
 
            # 둘이 겹쳐있을경우 더 많이 이동한 구슬을 1칸 뒤로 보낸다.
            if nrx == nbx and nry == nby:
                if rcnt > bcnt:
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
 
            # 탐색하지 않은 방향 탐색
            if (nrx, nry, nbx, nby) not in visited:
                visited.append((nrx, nry, nbx, nby))
                q.append((nrx, nry, nbx, nby, result + 1))
                
    # 빨간 구슬 꺼낼 방법이 없는 경우
    print(-1)
 
bfs()