[백준(BOJ)] #13459- 구슬 탈출 (파이썬, PyPy3)

문제

 

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

13459번: 구슬 탈출

 

---

문제 풀이

구현 문제로 BFS 알고리즘을 사용하여 빼낼 수 있는지 없는지를 알 수 있습니다.

2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

 

1) 빨간색(R), 파란색(B) 구슬은 보드를 상하좌우로 기울여 동시에 이동한다. 따라서 두 구슬의 좌표를 큐에 삽입하고 빼주면서 이동하는 작업을 한다.

2) 벽(#) 또는 구멍(O)이 나올 때까지 한 턴에 두 구슬을 이동시킨다. 만약 파란색(B) 구슬이 구멍의 위치에 도달하면 해당 방향으로의 더 이상 작업은 생략한다.

3) 두 구슬이 같은 좌표에 위치하게 된다면 이동한 방향에 따라서 더 많이 이동한 구슬을 뒤에 배치한다.

4) 한 턴 이동을 완료한 구슬들의 좌표가 위치한 적 없는 좌표이면 큐에 삽입해 다음 이동을 할 수 있도록 한다.

5) 10턴 안에 빨간색(R) 구슬의 위치가 구멍의 위치에 도달하면 1을 출력해주고 종료한다. 그게 아니면 0 출력 종료

 

---

구현

코드

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

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

def bfs(red_p, blue_p):
    dq = deque()
    check_set = set()
    count = 0
    
    dq.append((red_p, blue_p))
    check_set.add((red_p, blue_p))
    while dq:
        # 한 턴
        for _ in range(len(dq)):
            t_red_p, t_blue_p = dq.popleft()
            # 기울인 턴이 10번 이상이면 0출력 종료
            if count > 10:
                print(0)
                return
            # 빨간 구슬의 위치가 구멍의 위치이면 1출력 종료
            if a[t_red_p[0]][t_red_p[1]] == 'O':
                print(1)
                return
            # 네 방향 기울임
            for i in range(4):
                red_x = t_red_p[0]
                red_y = t_red_p[1]
                blue_x = t_blue_p[0]
                blue_y = t_blue_p[1]  
                # 벽을 만나거나 구멍을 만날 때 까지 이동
                while True:
                    red_x += dx[i]
                    red_y += dy[i]
                    if a[red_x][red_y] == '#':
                        red_x -= dx[i]
                        red_y -= dy[i]
                        break
                    elif a[red_x][red_y] == 'O':
                        break
                while True:
                    blue_x += dx[i]
                    blue_y += dy[i]
                    if a[blue_x][blue_y] == '#':
                        blue_x -= dx[i]
                        blue_y -= dy[i]
                        break
                    elif a[blue_x][blue_y] == 'O':
                        break
                # 파란 구슬이 구멍에 위치하면 아래 작업 생략
                if a[blue_x][blue_y] == 'O':
                    continue
                # 빨간 구슬의 위치와 파란 구슬의 위치가 같으면 더 많이 이동한 구슬을 이동한 방향에 따라 뒤에 배치
                if (red_x, red_y) == (blue_x, blue_y):
                    if abs(red_x - t_red_p[0]) + abs(red_y - t_red_p[1]) > abs(blue_x - t_blue_p[0]) + abs(blue_y - t_blue_p[1]):
                        red_x -= dx[i]
                        red_y -= dy[i]
                    else:
                        blue_x -= dx[i]
                        blue_y -= dy[i]
                # 위치한 적 없는 위치이면 큐에 넣고 히스토리 추가
                if ((red_x, red_y), (blue_x, blue_y)) not in check_set:
                    dq.append(((red_x, red_y), (blue_x, blue_y)))
                    check_set.add(((red_x, red_y), (blue_x, blue_y)))
        count += 1
    print(0)

if __name__ == "__main__":
    n, m = map(int, input().split())
    a = [list(input().rstrip()) for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if a[i][j] == 'R':
                red_p = (i, j)
            if a[i][j] == 'B':
                blue_p = (i, j)
                
    bfs(red_p, blue_p)

결과