[Baekjoon] 13460번 : 구슬 탈출 2 (Python, 구현, BFS)

[Baekjoon] 13460번 : 구슬 탈출 2 (Python, 구현, BFS)

 

목차

 

 

 

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

13460번: 구슬 탈출 2

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 32528KB / 시간 92ms / 코드 길이 1479B

 

해당 문제는 파란색 구슬보다 빠르게 빨간색 구슬이 10회 이내 탈출할 수 있는지를 묻는 문제이다.

 

이번 문제를 풀기 위해서 고려해야하는 것

 

1) 구슬은 일직선으로 움직인다. (move 함수를 사용)

 

2) BFS를 사용할 때 방문 처리를 위해서는 빨간색 구슬과 파란색 구슬의 위치를 한 번에 고려해야 한다. (visit list)

 

3) 4방향에 대해 움직일 때 변경된 위치를 기준으로 여러 가지를 고려해야한다.

3)-(1) 파란색이 출구에 먼저 도착하면 안 된다.

3)-(2) 일직선으로 움직이기 때문에 파란색 구슬과 빨간색 구슬이 겹칠 때가 존재한다. 이를 위한 처리가 필요하다. (움직이는 횟수를 count한다. 만약 count가 더 많다면 더 많이 움직였다는 의미이고 이는 더 많이 움직인 구슬을 한 단계 이전으로 되돌린다.)

3)-(3) 변경된 위치의 빨간색 구슬와 파란색 구슬의 방문 처리(visit)와 함께 queue에 추가한다.

3)-(4) 움직인 횟수가 10번이 넘어가면 -1 출력, 만약 그 이전에 빨간색 구슬이 출구를 찾아내면 횟수 출력

 

 

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

n, m = map(int, input().split())
l=[]
for i in range(n):
    l.append(list(input().rstrip()))
    for j in range(m):
        if l[i][j] == 'R':
            rx, ry = i,j
        elif l[i][j] == 'B':
            bx, by = i, j

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visit = [[[[False] * m for i in range(n)] for i in range(m)] for i in range(n)]

def move(i, j, dx, dy):
    c = 0
    while l[i+dx][j+dy] != '#' and l[i][j] != 'O':
        i += dx
        j += dy
        c += 1
    return i, j, c

def bfs(rx, ry, bx, by, d):
    q = deque()
    q.append([rx,ry,bx,by, d])
    visit[rx][ry][bx][by] = True

    while q:
        rx, ry, bx, by, d = q.popleft()
        if d > 10:
            break
        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i])
            nbx, nby, bc = move(bx, by, dx[i], dy[i])
            if l[nbx][nby] != 'O':
                if l[nrx][nry] == 'O':
                    print(d)
                    return
                if nrx == nbx and nry == nby:
                    if rc > bc:
                        nrx -= dx[i]
                        nry -= dy[i]
                    else:
                        nbx -= dx[i]
                        nby -= dy[i]

                if not visit[nrx][nry][nbx][nby]:
                    visit[nrx][nry][nbx][nby] = True
                    q.append([nrx, nry, nbx, nby, d+1])
                    print(q)
    print(-1)

bfs(rx, ry, bx, by, 1)