Python 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

항상 알고리즘 문제를 익숙한 자바스크립트로 풀다가, 생각보다 많은 기업에서 자바스크립트 사용이 불가능한걸 알게되어

이제부터 파이썬으로 알고리즘 공부를 하려고 한다!

 

✅ 문제 정리

왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울이기
빨간 구슬이 구멍에 빠지면 성공
실패: 파란 구슬이 구멍이 빠지면 or 파란 구슬과 빨간 구슬이 동시에 빠지면 실패
두 구슬은 동시에 같은 칸에 있을 수 없다
. 은 빈칸
# 은 장애물 또는 벽
0 은 구멍의 위치
R 은 빨간 구슬
B 는 파란 구슬
보드의 가장자리에는 모두 #이 있다
output: 최소 몇 번 만에 빨간 구슬을 구멍으로 빼낼 수 있는지 출력하기
10번 이하로 움직여서 구멍으로 뺴낼 수 없으면 -1 출력

 

 

✅ 코드

from collections import deque
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]

# rx, ry, bx, by에 빨간 구슬과 파란 구슬의 위치를 저장
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'R':
            rx, ry = i, j
        elif graph[i][j] == 'B':
            bx, by = i, j

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs (rx, ry, bx, by):
    q = deque()
    # q 초기화하기
    q.append((rx, ry, bx, by, 0))
    visited = [(rx, ry, bx, by)]
    
    while q:
        rx, ry, bx, by, depth = q.popleft()
        if depth > 10: # 이동 횟수가 10번을 넘으면 -1 출력
            print(-1)
            return
        if graph[rx][ry] == 'O': # 빨간 구슬이 구멍에 위치하면 이동 횟수 출력
            print(depth)
            return
        for i in range(4): # 상, 하, 좌, 우 4방향 탐색
            nrx, nry, rcount = rx, ry, 0
            while True: # 빨간 구슬이 이동한 위치 계산
                nrx += dx[i]
                nry += dy[i]
                rcount += 1 # 구슬의 이동한 거리
                if graph[nrx][nry] == '#': # 구슬의 위치가 벽이면 그 전 칸으로 다시 이동
                    nrx -= dx[i]
                    nry -= dy[i]
                    break
                if graph[nrx][nry] == 'O': # 구슬이 구멍에 빠지면 중단
                    break
            nbx, nby, bcount = bx, by, 0
            while True: # 파란 구슬이 이동한 위치 계산
                nbx += dx[i]
                nby += dy[i]
                bcount += 1
                if graph[nbx][nby] == '#':
                    nbx -= dx[i]
                    nby -= dy[i]
                    break
                if graph[nbx][nby] == 'O':
                    break
            if graph[nbx][nby] == 'O': # 파란 구슬이 구멍에 빠진 경우
                continue

            if nrx == nbx and nry == nby: # 두 구슬의 위치가 같은 경우
                if rcount > bcount: # 두 구슬이 같은 위치에 있을 수 없으므로, 이동 거리가 더 많은 구슬을 한칸 뒤로 옮김
                    nrx -= dx[i]
                    nry -= dy[i]
                else:
                    nbx -= dx[i]
                    nby -= dy[i]
            if (nrx, nry, nbx, nby) not in visited: # 빨간 구슬과 파란 구슬의 위치에 방문한 적이 없다면
                q.append((nrx, nry, nbx, nby, depth+1))
                visited.append((nrx, nry, nbx, nby))

    print(-1)

bfs(rx, ry, bx, by)