[PS - Baekjoon] 13460번 구슬탈출2

안녕하세요 배트맨🦇 입니다 !

오늘은 BFS 문제인 "BOJ 13460번 - 구슬 탈출2" 을 풀어보려고 합니다.

삼성 코딩테스트 기출문제 중 난이도 상 문제로 알려져 있는 문제 이기도 합니다.

풀이가 궁금하신 분들께 도움이 됐으면 합니다.

---

13460 : 구슬 탈출2

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

골드1 티어의 문제입니다. 이번 문제는 BFS를 이용해 풀이를 진행하려 합니다. 삼성 코테 문제답게 문제에 대한 스토리 설명이 엄청 깁니다ㅎㅎ

문제를 요약하면 직사각형의 미로 같은 보드에 빨간색과 파란색 구슬이 들어있고, 그것을 상하좌우 네 방향으로 굴려서 빨간색 구슬이 목적지인 O표시 구멍에 들어가게 하는 문제입니다.

상하좌우 중 한 방향으로 굴릴 때에는 두 구슬이 벽에 닿거나 빨간 구슬이 구멍에 들어가는 등 더 이상 구르지 못할 때까지 굴립니다. 굴린 횟수가 총 10이 넘으면 -1을 출력하고 종료합니다.

'.' 은 구슬이 통과할 수 있는 칸을 의미하고,

'#' 는 벽을 의미하며, 구슬이 통과할 수 없는 칸입니다.

'O' 는 최종 목적지인 구멍, 'R'과 'B'는 각각 구슬을 의미합니다.

보드의 크기는 10x10 보다 작고 10번 이하로 굴려야 하기 때문에 시간제한 2초는 큰 무리가 없을 듯 보입니다.

단, 구슬이 같은 위치에 있거나, 파란 구슬이 구슬이 구멍에 들어가는 경우 등 예외를 잘 체크해야 합니다.

---

Solution

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
q = deque()

queue를 구현하기 위해 deque 라이브러리를 import 했습니다.

R과 B의 위치에 대해 방문했는지 확인할 때 두 구슬의 위치 모두에 대해 확인해야 하기 때문에 check 리스트를 4중 list로 선언했습니다.

def pos_init():
    rx, ry, bx, by = 0, 0, 0, 0  
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                rx, ry = i, j
            elif board[i][j] == 'B':
                bx, by = i, j
    
    q.append((rx, ry, bx, by, 1))
    check[rx][ry][bx][by] = True

pos_init() 함수는 R과 B의 초기 위치를 q에 append하기 위한 함수입니다. q에 append 할 때 마지막 1의 의미는 판을 움직인 횟수를 의미합니다.(이후 main 함수에서 움직인 횟수가 11부터는 반복문에서 탈출하도록 처리합니다)

def move(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

move() 함수는 parameter로 현재 위치와 진행 방향을 받습니다. 구슬의 진행방향에 있어 다음칸이 #이거나 현재칸이 O인 경우를 제외하고는 구슬이 진행하도록 합니다.(다음칸에 다른 구슬이 있는 예외는 main 함수에서 처리할 예정입니다)

def main():
    pos_init()

    while q:
        rx, ry, bx, by, depth = q.popleft()

        if depth > 10:
            break
        
        for i in range(4):
            rnx, rny, rcnt = move(rx, ry, dx[i], dy[i])
            bnx, bny, bcnt = move(bx, by, dx[i], dy[i])
            
            if board[bnx][bny] != 'O':
                if board[rnx][rny] == 'O':
                    return depth
                
                if rnx == bnx and rny == bny:
                    if rcnt > bcnt:
                        rnx -= dx[i]
                        rny -= dy[i]
                    else:
                        bnx -= dx[i]
                        bny -= dy[i]
                    
                if not check[rnx][rny][bnx][bny]:
                    check[rnx][rny][bnx][bny] = True
                    q.append((rnx, rny, bnx, bny, depth+1))
    
    return -1

main 코드에서 체크해야 할 부분은 R과 B가 같은 위치에 있을 때입니다.

다음은 전체 코드입니다.

#BFS #구슬탈출
import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
check = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
q = deque()

def pos_init():
    rx, ry, bx, by = 0, 0, 0, 0  
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                rx, ry = i, j
            elif board[i][j] == 'B':
                bx, by = i, j
    
    q.append((rx, ry, bx, by, 1))
    check[rx][ry][bx][by] = True

def move(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 main():
    pos_init()

    while q:
        rx, ry, bx, by, depth = q.popleft()

        if depth > 10:
            break
        
        for i in range(4):
            rnx, rny, rcnt = move(rx, ry, dx[i], dy[i])
            #print('move RED', rnx, rny)
            bnx, bny, bcnt = move(bx, by, dx[i], dy[i])
            #print('move BLUE', bnx, bny)
            if board[bnx][bny] != 'O':
                if board[rnx][rny] == 'O':
                    return depth
                
                if rnx == bnx and rny == bny:
                    if rcnt > bcnt:
                        rnx -= dx[i]
                        rny -= dy[i]
                    else:
                        bnx -= dx[i]
                        bny -= dy[i]
                    
                if not check[rnx][rny][bnx][bny]:
                    check[rnx][rny][bnx][bny] = True
                    q.append((rnx, rny, bnx, bny, depth+1))
    
    return -1

res = main()
print(res)

---

결과