[백준] 13459번 - 구슬 탈출 (파이썬)

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

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

# . # 0 R B => 빈칸, 장애물, 구멍, 빨간구슬, 파란구슬
N, M = map(int, input().split())
arr = []
red_x, red_y = 0, 0
blue_x, blue_y = 0, 0
for i in range(N):
    arr.append(list(input().strip()))
    for j in range(len(arr[i])):
        if arr[i][j] == 'R':
            red_x, red_y = i, j
            arr[i][j] = '.'
        elif arr[i][j] == 'B':
            blue_x, blue_y = i, j
            arr[i][j] = '.'
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


def move(x, y, dx, dy):
    nx, ny = x, y
    moving = 0
    while True:
        if arr[nx+dx][ny+dy] != '#' and arr[nx+dx][ny+dy] != 'O':
            nx += dx
            ny += dy
            moving += 1
        else:
            break
    return nx, ny, moving


def bfs():
    q = deque()
    q.append((red_x, red_y, blue_x, blue_y, 0))
    while q:
        x, y, a, b, count = q.popleft()
        if count > 10:
            continue
        for k in range(4):
            nx, ny, Rmove = move(x, y, dx[k], dy[k])
            na, nb, Bmove = move(a, b, dx[k], dy[k])

            if arr[na+dx[k]][nb+dy[k]] == 'O':
                continue
            if arr[nx+dx[k]][ny+dy[k]] == 'O' and count < 10:
                return 1

            if nx == na and ny == nb:
                if Rmove > Bmove:
                    nx -= dx[k]
                    ny -= dy[k]
                else:
                    na -= dx[k]
                    nb -= dy[k]
            if x == nx and y == ny and na == a and nb == b:
                continue
            q.append((nx, ny, na, nb, count+1))
    return 0


result = bfs()
print(result)

 

BFS

1. 입력을 받으면서 R의 위치와 B의 위치를 저장한다

2. result = 탐색 반환값 (bfs)

    - 빨간구슬의 좌표, 파란구슬의 좌표, 총 횟수가 q의 내용물이다.

    - 총 횟수가 10보다 크면 continue

    - 현재 구슬들의 위치에서 4방향으로 이동(move)

    - 특정방향으로 이동 (move) : 특정방향으로 이동할 수 있을 때까지 이동한다.

    - 만약 파란구슬의 위치가 'O'이면 continue, 빨간구슬의 위치가 'O'고 count가 10보다 작으면 return 1

    - 만약 파란 구슬과 빨간 구슬의 위치가 같다면 이동한 횟수가 더 큰 구슬을 한단계 전으로 배치

    - 만약 둘다 전의 위치이면 continue

    - 변경된 값들을 q에 append

3. result 출력