[백준] 13460 구슬 탈출 2

문제

www.acmicpc.net/problem/13460

 

코드

"""
성공 조건: 빨간 구슬을 구멍에 빠뜨리기
실패 조건
1. 파란 구슬이 구멍에 빠지면 실패.
2. 빨간 구슬, 파란 구슬 동시에 구멍에 빠져도 실패.
3. 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있을 수 없다.
4. 10번 이하로 움직여서 빨간 구슬을 구멍으로 빼낼 수 없으면 실패.
"""
from collections import deque

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(str, input())))
visit = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
q = deque()

def main():
    rx, ry, bx, by = [0] * 4
    for i in range(n): # R, B 구슬 위치 찾기
        for j in range(m):
            if graph[i][j] == 'R':
                rx, ry = i, j
            if graph[i][j] == 'B':
                bx, by = i, j
    q.append((rx, ry, bx, by, 0))
    visit[rx][ry][bx][by] = True

def move(x, y, dx, dy, c):
    while graph[x + dx][y + dy] != '#' and graph[x][y] != 'O':
        x += dx
        y += dy
        c += 1

    return x, y, c

def bfs():
    while q:
        rx, ry, bx, by, count = q.popleft()
        if count >= 10: # 조건 4. 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력
            print(-1)
            return

        for i in range(4):
            nrx, nry, rc = move(rx, ry, dx[i], dy[i], 0)
            nbx, nby, bc = move(bx, by, dx[i], dy[i], 0)

            if graph[nbx][nby] == 'O': # 조건 2. 파란 구슬이 구멍에 빠질 경우
                continue
            if graph[nrx][nry] == 'O': # 성공 조건. 빨간 구슬이 구멍에 빠지면 성공.
                print(count + 1)
                return
            if nrx == nbx and nry == nby: # 조건 3. 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있으면 안된다.
                if rc > bc: # 빨간 구슬과 파란 구슬 위치가 같으면 이동거리가 더 긴 구슬 위치를 -1 해주기
                    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, count + 1))
    print(-1)

main()
bfs()

 

풀이

1. 빨간, 파란 구슬의 (x, y) 좌표를 queue에 넣는다.
2. BFS를 이용해 구슬을 이동시킨다.
   1. nx, ny가 벽이 아니고, x, y가 구멍이 아니면 이동.
3. 구슬의 현재 위치가 구멍일 때:
   1. 파란 구슬의 위치가 구멍이라면 continue
   2. 빨간 구슬의 위치가 구멍이라면 1을 출력하고 종료
4. 빨간 구슬의 위치와 파란 구슬의 위치가 같으면 이동 거리가 더 긴 구슬 위치를 -1 해주기
5. 10번 이하로 움직여 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1 출력.