Baekjoon 13460. 구슬 탈출 2 / Python

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

알고리즘 설명

1. 입력 처리:
   • n, m을 입력받고 보드 상태를 arr 리스트에 저장합니다.
   • 보드를 탐색하면서 빨간 구슬, 파란 구슬, 구멍의 위치를 저장합니다.
2. 구슬 이동 함수:
   • move(x, y, dx, dy) 함수는 주어진 방향 dx, dy로 구슬을 이동시켜 최종 위치와 이동한 거리를 반환합니다.
3. BFS 탐색:
   • 초기 상태(빨간 구슬, 파란 구슬 위치, 움직임 횟수)를 큐에 추가합니다.
   • 큐에서 상태를 꺼내 네 방향으로 구슬을 이동시키고, 각 방향으로 이동한 후의 상태를 큐에 추가합니다.
   • 이동한 후, 파란 구슬이 구멍에 빠지지 않았고 빨간 구슬이 구멍에 빠졌다면 성공을 의미합니다.
   • 만약 빨간 구슬과 파란 구슬이 같은 위치에 있다면, 더 많이 이동한 구슬을 한 칸 뒤로 이동시킵니다.
   • 방문한 적이 없는 상태라면 그 상태를 큐에 추가합니다.
   • 10번 이상 움직여도 빨간 구슬이 구멍에 빠지지 않으면 실패로 간주합니다.

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

# 보드의 세로 크기 n과 가로 크기 m을 입력
n, m = map(int, input().split())
arr = []  # 보드의 상태를 저장할 리스트

# 보드의 상태를 입력받아 arr 리스트에 저장
for i in range(n):
    tmp = list(map(str, input().strip()))  # 각 줄을 문자열로 입력받아 리스트로 변환
    arr.append(tmp)  # 변환된 줄을 arr에 추가
    for j in range(m):
        if tmp[j] == 'R':  # 빨간 구슬의 위치
            red_x, red_y = i, j
        if tmp[j] == 'B':  # 파란 구슬의 위치
            blue_x, blue_y = i, j
        if tmp[j] == 'O':  # 구멍의 위치
            goal_x, goal_y = i, j

# 구슬을 이동시키는 함수
def move(x, y, dx, dy):
    cnt = 0  # 이동한 칸 수를 저장
    nx, ny = x, y  # 현재 위치를 nx, ny에 저장
    # 벽에 부딪히거나 구멍에 도달할 때까지 구슬을 이동
    while arr[nx + dx][ny + dy] != '#' and arr[nx][ny] != 'O':
        nx += dx  # x 방향으로 이동
        ny += dy  # y 방향으로 이동
        cnt += 1  # 이동한 칸 수 증가
    return nx, ny, cnt  # 최종 위치와 이동한 칸 수를 반환

q = dq()  # BFS를 위한 큐를 초기화

# 문제를 해결하는 함수
def solution():
    visited = {}  # 방문한 상태를 저장할 딕셔너리
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우 방향을 저장
    q.append([red_x, red_y, blue_x, blue_y, 0])  # 초기 상태를 큐에 추가

    while q:
        rx, ry, bx, by, cnt = q.popleft()  # 큐에서 현재 상태를 꺼냄
        if cnt >= 10:  # 10번 이상 움직이면 실패
            return -1

        for dx, dy in direction:  # 모든 방향에 대해
            # 빨간 구슬과 파란 구슬을 이동
            red_nx, red_ny, r_cnt = move(rx, ry, dx, dy)
            blue_nx, blue_ny, b_cnt = move(bx, by, dx, dy)

            if arr[blue_nx][blue_ny] != 'O':  # 파란 구슬이 구멍에 빠지지 않았으면
                if arr[red_nx][red_ny] == 'O':  # 빨간 구슬이 구멍에 빠지면 성공
                    return cnt + 1

                if red_nx == blue_nx and red_ny == blue_ny:  # 두 구슬이 겹치면
                    if r_cnt > b_cnt:  # 이동 거리가 더 긴 구슬을 한 칸 뒤로 이동
                        red_nx, red_ny = red_nx - dx, red_ny - dy
                    else:
                        blue_nx, blue_ny = blue_nx - dx, blue_ny - dy

                # 방문한 적이 없는 상태면 큐에 추가
                if (red_nx, red_ny, blue_nx, blue_ny) not in visited:
                    visited[(red_nx, red_ny, blue_nx, blue_ny)] = 1
                    q.append([red_nx, red_ny, blue_nx, blue_ny, cnt + 1])
    return -1  # 모든 경우를 다 탐색했지만 성공하지 못하면 -1을 반환

print(solution())