DFS - 13460번: 구슬 탈출 2

n, m = map(int, input().split())
maps = []
r_x = 0
r_y = 0
b_x = 0
b_y = 0

# maps = [list(input().rstrip()) for _ in range(n)]


for i in range(n):
    string = input()
    line = []
    for j in range(m):
        line.append(string[j])
        if string[j] == "R":
            r_x, r_y = i, j
        elif string[j] == "B":
            b_x, b_y = i, j
    maps.append(line)

dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

# 중요: 구슬이 같은 위치에 위치하면, 둘 중 더 많이 움직인 구슬을 한칸 뒤로 빽하기


def move(turn, maps, r_x, r_y, b_x, b_y, di):
    # 흔든 횟수가 10회를 넘어가면 실패
    if turn > 10:
        return -1, -1, -1, -1, -1
    # 구슬 2개 di 방향으로 이동시키기
    # 보드판 길이는 최대 10이므로
    r_cnt = 0
    b_cnt = 0
    r_is_hole = False
    b_is_hole = False
    for i in range(10):
        rnx, rny = r_x + dx[di], r_y + dy[di]
        bnx, bny = b_x + dx[di], b_y + dy[di]
        # 블루가 구멍에 빠지면 실패
        if maps[bnx][bny] == "O":
            b_is_hole = True

        # 레드가 구멍에 빠지면 성공
        if maps[rnx][rny] == "O":
            r_is_hole = True

        # 레드가 가려는 곳이 벽이 아니라면 이동
        if maps[rnx][rny] != "#":
            r_x = rnx
            r_y = rny
            # 이동 거리 증가
            r_cnt += 1
        if maps[bnx][bny] != "#":
            b_x = bnx
            b_y = bny
            b_cnt += 1

        # 둘 다 더 갈 곳이 없다면 종료
        if maps[rnx][rny] == "#" and maps[bnx][bny] == "#":
            break

    # 레드와 블루가 이동을 했는데 서로 위치가 겹친다면
    if r_x == b_x and r_y == b_y:
        # 둘 중 이동거리가 더 큰 걸 한 칸 뒤로 빼기
        if b_cnt > r_cnt:
            b_x = b_x - dx[di]
            b_y = b_y - dy[di]
        else:
            r_x = r_x - dx[di]
            r_y = r_y - dy[di]

    # 둘 다 더 이상 움직이지 않으면
    if b_cnt == 0 and r_cnt == 0:
        return -1, -1, -1, -1, -1
    # 블루가 구멍에 빠지면 실패
    elif b_is_hole:
        return -1, -1, -1, -1, -1
    # 레드 블루 둘 다 구멍에 빠지면 실패
    elif r_is_hole and b_is_hole:
        return -1, -1, -1, -1, -1
    # 레드만 빠지면 성공, 걸린 횟수 리턴
    elif r_is_hole:
        return turn, r_x, r_y, b_x, b_y
    # 움직였는데 아직 구멍에 안빠졌으면 0과 좌표 리턴
    else:
        return 0, r_x, r_y, b_x, b_y


def dfs(maps, r_x, r_y, b_x, b_y, turn, di):

    res, r_x2, r_y2, b_x2, b_y2 = move(turn, maps, r_x, r_y, b_x, b_y, di)
    if res == -1:
        return -1

    elif res == 0:
        # 한번 더 흔들기
        min_res = 100
        for next_di in range(4):
            # 이전과 동일한 방향이면 패스
            if next_di == di:
                continue
            dfs_res = dfs(maps, r_x2, r_y2, b_x2, b_y2, turn + 1, next_di)
            if dfs_res is not None and dfs_res != -1:
                min_res = min(min_res, dfs_res)
        # 갱신 안되었다면 실패이므로
        if min_res == 100:
            return -1
        return min_res

    elif res > 0:
        return res


turn = 1
min_turn = 100
for di in range(4):
    res = dfs(maps, r_x, r_y, b_x, b_y, turn, di)
    # 성공 시에만 최소 횟수로 갱신
    if res != -1 and res is not None:
        min_turn = min(min_turn, res)
# 최솟값 갱신이 안되었다면 실패이므로로
if min_turn == 100:
    print("-1")
else:
    print(min_turn)