[백준] 구슬 탈출 2

구슬 탈출 2

구슬 탈출 2

코드

import sys
from collections import deque

def bfs(board, red, blue):
    q = deque()
    count = 0

    q.append((red, blue, count))

    while q:
        red_pos, blue_pos, cnt = q.popleft()

        if cnt >= 10:
            return print(-1)

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

        rank = 0

        for i in range(4):
            if i == 0:#상 일때
                if red_pos[0] < blue_pos[0]:
                    rank = 0
                else:
                    rank = 1
            elif i == 1:#하 일때
                if red_pos[0] > blue_pos[0]:
                    rank = 0
                else:
                    rank = 1
            elif i == 2:#좌
                if red_pos[1] < blue_pos[1]:
                    rank = 0
                else:
                    rank = 1
            else:#우
                if red_pos[1] > blue_pos[1]:
                    rank = 0
                else:
                    rank = 1

            # rank가 0이면 빨간공이 더 앞에
            # rank가 1이면 파란공이 더 앞에

            red_nx = red_pos[0]
            red_ny = red_pos[1]
            blue_nx = blue_pos[0]
            blue_ny = blue_pos[1]

            flag = False

            while True:
                if board[red_nx + dx[i]][red_ny + dy[i]] != "#":
                    if board[red_nx + dx[i]][red_ny + dy[i]] != "O":
                        red_nx += dx[i]
                        red_ny += dy[i]
                    elif board[red_nx + dx[i]][red_ny + dy[i]] == "O":
                        flag = True
                        break
                        # 빨간색이 홀에 빠졌을 경우 파란색도 빠지는걸 체크하기 위해 flag를 True로 바꿔줌
                elif board[red_nx + dx[i]][red_ny + dy[i]] == "#":
                    flag = False
                    break
                    # 빨간색이 더 이상 전진할 수 없을 때 빠져나옴

            while True:
                if board[blue_nx + dx[i]][blue_ny + dy[i]] != "#":
                    if board[blue_nx + dx[i]][blue_ny + dy[i]] != "O":
                        blue_nx += dx[i]
                        blue_ny += dy[i]
                    elif board[blue_nx + dx[i]][blue_ny + dy[i]] == "O":
                        flag = False
                        break
                        # 파란색이 홀에 빠지면 안됨
                elif board[blue_nx + dx[i]][blue_ny + dy[i]] == "#":
                    if flag == True:
                        # 파란색은 홀에 안빠졌지만, 빨간색이 홀에 빠진 경우
                        return print(cnt + 1)
                    else:
                        if red_nx == blue_nx and red_ny == blue_ny:
                            # 빨간공과 파란공의 위치가 같은 경우
                            if rank == 0:
                                # 빨간공이 더 앞에 있어야 하는 경우
                                blue_nx -= dx[i]
                                blue_ny -= dy[i]

                            else:
                                # 파란공이 더 앞에 있어야 하는 경우
                                red_nx -= dx[i]
                                red_ny -= dy[i]
                        if red_pos != (red_nx, red_ny) or blue_pos != (blue_nx, blue_ny):
                            q.append(((red_nx, red_ny), (blue_nx, blue_ny), cnt + 1))
                        break
            flag = False
    return print(-1)

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())

    board = []

    for i in range(n):
        board.append(list(sys.stdin.readline().rstrip()))

    red = (0, 0)
    blue = (0, 0)

    for i in range(n):
        for j in range(m):
            if board[i][j] == 'B':
                blue = (i, j)
            elif board[i][j] == 'R':
                red = (i, j)

    bfs(board, red, blue)