BOJ_13460_구슬 탈출2

10번 이하로 움직일 수 있으며, 빨간 구슬이 들어가도록 하는 최소 움직임 횟수를 구한다
단, 파란 구슬이 들어가거나, 두 구슬이 동시에 들어가서도 안 된다

사방으로 구슬을 보내면서 성공할 시 최솟값을 갱신하면 된다. 구슬은 길이 이어지지 않을 때까지 앞으로 보내면 된다. 동시에 이동할 경우, 방향에 따라 해당 방향 기준 더 앞에 있는 구슬을 먼저 보낸다. 그렇게 하지 않으면 구슬을 움직일 때 오차가 생긴다.

음의 방향으로 이동할 때와 양의 방향으로 이동할 때의 대소 비교가 반대이기 때문에 위치를 비교할 때 dx, dy의 값을 곱해주었다

order = False if b_idx[0] * dx[i] > r_idx[0] * dx[i] else True
order = False if b_idx[1] * dy[i] > r_idx[1] * dy[i] else True

예를 들어 rx = 2, bx = 3일 때 오른쪽 방향 진로는 2 < 3이므로 b를 먼저 보내고 왼쪽 방향 진로는 -2 > -3 이 되어서 r을 먼저 보내게 된다

삽질

구슬 바로 주변에 벽이라면 진행을 갱신하는 의미가 없기 때문에 사방을 한 칸 확인 후 dfs를 실행하지 않았다.

빨간 구슬만 확인하면 된다고 생각해서(왜 그랬을까?) 빨간 구슬이 안 움직이는 걸 조건으로 작성했는데, 그러면 안 되고 두 구슬이 모두 해당 진행 방향으로 갈 수 없을 때를 조건으로 넣어줘야 한다. 왜냐면 파란 구슬이 먼저 들어갈 수도 있는 것이고, 파란 구슬의 위치가 달라져 빨간 구슬이 들어갈 수 있게 되기도 하기 때문이다.

# 파란 구슬 구멍에 들어가면 안 됨  
# 기울여서 구슬로 빼내기  
# 더 이상 구슬이 움직이지 않을 때 -> 끝에 걸릴 때까지 기울여둔다  
#  
# 최소 몇 번만에? 못 하면 -1#  
# dfs로 사방으로 보내고, 최솟값 갱신  
import copy  
import sys  
  
dx = [-1, 1, 0, 0]  
dy = [0, 0, -1, 1]  
  
# 입력  
N, M = list(map(int, input().split()))  
board_origin = []  
b_start = ()  
r_start = ()  
min_cnt = sys.maxsize  
  
for i in range(N):  
    board_origin.append(list(input()))  
  
    if 'B' in board_origin[i]:  
        b_start = (i, board_origin[i].index('B'))  
  
    if 'R' in board_origin[i]:  
        r_start = (i, board_origin[i].index('R'))  
  
  
def four_dir(b_idx, r_idx, cnt, board):  
    global min_cnt  
    if cnt > 10 or cnt >= min_cnt:  
        return  
  
    for i in range(4):  
        # 바로 막혀있다면 진입 안 함  
        if board[r_idx[0] + dx[i]][r_idx[1] + dy[i]] == '#' and board[b_idx[0] + dx[i]][b_idx[1] + dy[i]] == '#':  
            continue  
  
        # 바로 막혀있진 않다면 진입  
        if i <= 1:  
            order = False if b_idx[0] * dx[i] > r_idx[0] * dx[i] else True  
  
        else:  
            order = False if b_idx[1] * dy[i] > r_idx[1] * dy[i] else True  
  
        dfs(b_idx, r_idx, order, i, cnt + 1, copy.deepcopy(board))  
  
  
# order : B가 앞이면 False, R이 앞이면 Truedef dfs(b_idx, r_idx, order, direction, cnt, board):  
    global min_cnt  
  
    if not order:  
        b_idx, b_flag = go_straight(b_idx, direction, board, 'B')  
        r_idx, r_flag = go_straight(r_idx, direction, board, 'R')  
  
    else:  
        r_idx, r_flag = go_straight(r_idx, direction, board, 'R')  
        b_idx, b_flag = go_straight(b_idx, direction, board, 'B')  
  
    # 실패  
    if b_flag:  
        return  
  
    # 성공  
    elif r_flag:  
        min_cnt = min(cnt, min_cnt)  
        return  
  
    four_dir(b_idx, r_idx, cnt, board)  
  
  
def go_straight(idx, direction, board, c):  
    x = idx[0]  
    y = idx[1]  
  
    while True:  
        x += dx[direction]  
        y += dy[direction]  
  
        if not (board[x][y] == 'O' or board[x][y] == '.'):  
            board[idx[0]][idx[1]] = '.'  
            board[x - dx[direction]][y - dy[direction]] = c  
  
            return (x - dx[direction], y - dy[direction]), False  
  
        elif board[x][y] == 'O':  
            board[idx[0]][idx[1]] = '.'  
            board[x][y] = 'O'  
            return idx, True  
  
  
four_dir(b_start, r_start, 0, board_origin)  
print(min_cnt if min_cnt < sys.maxsize else -1)