[백준] 구슬탈출 1~2

🔔 문제

• 백준 13459번: 구슬탈출 (https://www.acmicpc.net/problem/13459)
• 백준 13460번: 구슬탈출 2 (https://www.acmicpc.net/problem/13460)

🎯 풀이방법

• 핵심
  • 구슬이 움직인 횟수(depth)와 구슬이 이동한 칸 수(count) 구분
  • 빨강 구슬과 파랑 구슬이 동시에 움직이기 때문에 구현 상에서 겹칠 경우 움직임이 많은 구슬이 한 칸 적어야함. (판단 이유는 아래 그림과 같음)
  • BFS 탐색
    1. Queue에 (빨강 구슬 위치, 파랑 구슬 위치, depth) 삽입
    2. Queue가 빌 때까지 While문 반복
       2-1. Popleft()
       2-2. depth가 10 초과이면 break
       2-3. 상하좌우 탐색
       2-3-1. 방향으로 빨강, 파랑 구슬 이동
       2-3-2. 파랑 구슬이 구멍에 떨어지면 continue
       2-3-3. 빨강 구슬이 구멍에 떨어지면 성공 (13459이면 1 출력, 13460이면 depth 출력)
       2-3-4. 빨강 구슬과 파랑 구슬이 동시에 같은 칸에 있다면 이동 거리가 많은 구슬을 한칸 뒤로 이동
       2-3-5. 방문하지 않았다면 queue에 삽입(append)
    3. 2번 과정에서 return되지 않았다면 실패한 것임 (13459이면 0 출력, 13460이면 -1 출력)

💡 이 문제에서 얻어갈 것

BFS + 시뮬레이션 문제

💻 Python code

import sys
from collections import deque

input = sys.stdin.readline

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


def init():
    rx, ry, bx, by = [0]*4
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                rx,ry = i,j
                board[i][j] = '.'
            elif board[i][j] == 'B':
                bx,by = i,j
                board[i][j] = '.'
    queue.append((rx,ry,bx,by,1))   # 위치 정보와 depth
    visited[rx][ry][bx][by] = True            


def move(x,y,dx,dy):
    count = 0  # 이동한 칸 수
    # 다음 이동이 벽이거나 구멍이 아닐때까지
    while board[x+dx][y+dy]!='#' and board[x][y]!='O':
        x += dx
        y += dy
        count += 1
    return x,y,count


def bfs():
    init()
    
    while queue:
        rx,ry,bx,by,depth = queue.popleft()
        if depth>10:
            break
        for i in range(len(dx)):
            next_rx, next_ry, r_count = move(rx, ry, dx[i], dy[i])  # RED
            next_bx, next_by, b_count = move(bx, by, dx[i], dy[i])  # BLUE
                        
            if board[next_bx][next_by] == 'O':  # 파란 구슬이 구멍에 떨어지면 Pass
                continue
            if board[next_rx][next_ry] == 'O':  # 빨간 구슬이 구멍에 떨어지면 성공
                print(depth)
                return
            if next_rx==next_bx and next_ry==next_by: # 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있을 수 없다
                if r_count > b_count:  # 이동거리가 많은 구슬이 한칸 뒤로
                    next_rx -= dx[i]
                    next_ry -= dy[i]
                else:
                    next_bx -= dx[i]
                    next_by -= dy[i]
            
            # BFS 탐색을 마치고 방문 여부 확인
            if not visited[next_rx][next_ry][next_bx][next_by]:
                visited[next_rx][next_ry][next_bx][next_by] = True
                queue.append((next_rx, next_ry, next_bx, next_by, depth+1))
    print(-1)
    
bfs()