2개의 사탕

 

백트래킹 없이는 시간 초과가 나는 문제였습니다.

그래서 딕셔너리에 현재의 위치와 방향을 key로 그리고 움직인 횟수를 value 갱신해줬더니 풀렸습니다. 헿

 

import sys, copy, math
from collections import deque
n, m = map(int, sys.stdin.readline().strip().split())
graph = [list(sys.stdin.readline().strip()) for _ in range(n)]
answer = math.inf
b_y, b_x = 0, 0
r_y, r_x = 0, 0
g_y, g_x = 0, 0
dy, dx = [-1, 0, 1, 0], [0, 1, 0, -1]
move_dict = {}
def find_first_candy(d, r_y, r_x, b_y, b_x):
    if d == 0: #왼쪽 기울일 때
        if r_x != b_x:
            return "Red"
        if r_y < b_y:
            return "Red"
        return "Blue"
    elif d == 1:
        if r_y != b_y:
            return "Red"
        if r_x > b_x:
            return "Red"
        return "Blue"
    elif d == 2:
        if r_x != b_x:
            return "Red"
        if r_y > b_y:
            return "Red"
        return "Blue"
    elif d == 3:
        if r_y != b_y:
            return "Red"
        if r_x < b_x:
            return "Red"
        return "Blue"

def find_red_blue_goal():
    global graph, n, m, b_y, b_x, r_y, r_x, g_y, g_x
    for y in range(n):
        for x in range(m):
            if graph[y][x] == "B":
                b_y, b_x = y, x
            elif graph[y][x] == "R":
                r_y, r_x = y, x
            elif graph[y][x] == "O":
                g_y, g_x = y, x

def validation(ny, nx):
    global n, m
    return 0 <= ny < n and 0 <= nx < m
    
def dfs(b_y, b_x, r_y, r_x, g_y, g_x, graph, count, d):
    # print(b_y, b_x, r_y, r_x, g_y, g_x, count, d)
    # for i in graph:
    #     print(i)
    # print()
    global answer, move_dict
    if (b_y, b_x, r_y, r_x, d) in move_dict:
        if move_dict[(b_y, b_x, r_y, r_x, d)] <= count:
            return
    move_dict[(b_y, b_x, r_y, r_x, d)] = count
    
    if count > 10:
        return

    tmp_graph = copy.deepcopy(graph)

    if b_y == -1 and r_y == -1:  #둘다 빠지면 그냥 return
        return
    if b_y != -1 and r_y == -1: 
        answer = min(answer, count)

    first_candy = find_first_candy(d, r_y, r_x, b_y, b_x)
    if first_candy == "Red":
        q = deque([])
        q.append((r_y, r_x))
        while q:
            y, x = q.popleft()
            ny = y + dy[d]
            nx = x + dx[d]
            if validation(ny, nx):
                if tmp_graph[ny][nx] == "#" or tmp_graph[ny][nx] == "B":
                    continue
                if tmp_graph[ny][nx] == ".":
                    tmp_graph[y][x], tmp_graph[ny][nx] = ".", "R"
                    r_y, r_x = ny, nx
                    q.append((ny, nx))
                    
                if tmp_graph[ny][nx] == "O":
                    tmp_graph[y][x] = "."
                    r_y, r_x = -1, -1
        q = deque([])
        q.append((b_y, b_x))
        while q:
            y, x = q.popleft()
            ny = y + dy[d]
            nx = x + dx[d]
            if validation(ny, nx):
                if tmp_graph[ny][nx] == "#" or tmp_graph[ny][nx] == "R":
                    continue
                if tmp_graph[ny][nx] == ".":
                    tmp_graph[y][x], tmp_graph[ny][nx] = ".", "B"
                    b_y, b_x = ny, nx
                    q.append((ny, nx))
                    
                if tmp_graph[ny][nx] == "O":
                    tmp_graph[y][x] = "."
                    b_y, b_x = -1, -1

    else:
        q = deque([])
        q.append((b_y, b_x))
        while q:
            y, x = q.popleft()
            ny = y + dy[d]
            nx = x + dx[d]
            if validation(ny, nx):
                if tmp_graph[ny][nx] == "#" or tmp_graph[ny][nx] == "R":
                    continue
                if tmp_graph[ny][nx] == ".":
                    tmp_graph[y][x], tmp_graph[ny][nx] = ".", "B"
                    b_y, b_x = ny, nx
                    q.append((ny, nx))
                    
                if tmp_graph[ny][nx] == "O":
                    tmp_graph[y][x] = "."
                    b_y, b_x = -1, -1

        q = deque([])
        q.append((r_y, r_x))
        while q:
            y, x = q.popleft()
            ny = y + dy[d]
            nx = x + dx[d]
            if validation(ny, nx):
                if tmp_graph[ny][nx] == "#" or tmp_graph[ny][nx] == "B":
                    continue
                if tmp_graph[ny][nx] == ".":
                    tmp_graph[y][x], tmp_graph[ny][nx] = ".", "R"
                    r_y, r_x = ny, nx
                    q.append((ny, nx))
                    
                if tmp_graph[ny][nx] == "O":
                    tmp_graph[y][x] = "."
                    r_y, r_x = -1, -1

    for d in range(4):
        dfs(b_y, b_x, r_y, r_x, g_y, g_x, tmp_graph, count + 1, d)
    
find_red_blue_goal()

for d in range(4):
    dfs(b_y, b_x, r_y, r_x, g_y, g_x, graph, 0, d)
    dfs(b_y, b_x, r_y, r_x, g_y, g_x, graph, 0, d)
    dfs(b_y, b_x, r_y, r_x, g_y, g_x, graph, 0, d)
    dfs(b_y, b_x, r_y, r_x, g_y, g_x, graph, 0, d)

if answer == math.inf:
    print(-1)
else:
    print(answer)