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

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

# 구슬 탈출 2
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 (count+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 -1


result = bfs()
print(result)

 

 

BFS

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

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

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

    - 총 횟수가 10보다 크면 continue

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

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

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

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

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

    - 변경된 값들을 q에 append

3. result 출력

 

구슬 탈출 : https://2hs-rti.tistory.com/83

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

구슬 탈출을 풀고나서 구현을 한문제 더 풀어보려고 찾다가 2도 풀어봤는데 코드가 똑같다.

바뀐거라고는 return할 때 count를 해주는 부분 뿐이다.

다음부터는 시리즈는 텀을 두고 풀어야겠다.