https://www.acmicpc.net/problem/13460

---

1. 코드

import copy


def dfs(idx, path):
    if idx==10:
        cases.append(path)
        return

    if path[-1] == 'u' or path[-1] == 'd':
        dfs(idx+1, path + ['l'])
        dfs(idx+1, path + ['r'])
    elif path[-1] == 'l' or path[-1] == 'r':
        dfs(idx+1, path + ['u'])
        dfs(idx+1, path + ['d'])


def left(x, y):
    k, og_x, og_y = graph[x][y], x, y
    graph[og_x][og_y] = '.'
    while graph[x][y-1] == '.' or graph[x][y-1] == 'O':
        if graph[x][y-1] == 'O':
            return -1, -1
        y -= 1
    graph[x][y] = k
    return x, y

def right(x, y):
    k, og_x, og_y = graph[x][y], x, y
    graph[og_x][og_y] = '.'
    while graph[x][y+1] == '.' or graph[x][y+1] == 'O':
        if graph[x][y+1] == 'O':
            return -1, -1
        y += 1
    graph[x][y] = k
    return x, y

def up(x, y):
    k, og_x, og_y = graph[x][y], x, y
    graph[og_x][og_y] = '.'
    while graph[x-1][y] == '.' or graph[x-1][y] == 'O':
        if graph[x-1][y] == 'O':
            return -1, -1
        x -= 1
    graph[x][y] = k
    return x, y

def down(x, y):
    k, og_x, og_y = graph[x][y], x, y
    graph[og_x][og_y] = '.'
    while graph[x+1][y] == '.' or graph[x+1][y] == 'O':
        if graph[x+1][y] == 'O':
            return -1, -1
        x += 1
    graph[x][y] = k
    return x, y


ans = 100
N, M = map(int, input().split())
og_graph = [list(map(str, input())) for _ in range(N)]
for i in range(N):
    for j in range(M):
        if og_graph[i][j] == 'R':
            og_red = [i, j]
        elif og_graph[i][j] == 'B':
            og_blue = [i, j]

cases = []
dfs(1, ['u'])
dfs(1, ['d'])
dfs(1, ['l'])
dfs(1, ['r'])

for case in cases:
    cnt = 1
    graph = copy.deepcopy(og_graph)
    red = copy.deepcopy(og_red)
    blue = copy.deepcopy(og_blue)

    for dir in case:
        if dir == 'u':
            bx, by = up(blue[0], blue[1])
            rx, ry = up(red[0], red[1])
            bx, by = up(bx, by)
        elif dir == 'd':
            bx, by = down(blue[0], blue[1])
            rx, ry = down(red[0], red[1])
            bx, by = down(bx, by)

        elif dir == 'l':
            bx, by = left(blue[0], blue[1])
            rx, ry = left(red[0], red[1])
            bx, by = left(bx, by)
        elif dir == 'r':
            bx, by = right(blue[0], blue[1])
            rx, ry = right(red[0], red[1])
            bx, by = right(bx, by)

        # 공통 로직
        if (bx, by) == (-1, -1):
            break  # 실패
        elif (rx, ry) == (-1, -1):
            ans = min(ans, cnt)  # 성공
            break
        else:
            red[0], red[1] = rx, ry
            blue[0], blue[1] = bx, by
        cnt += 1

if ans == 100:
    print(-1)
else:
    print(ans)

2. 후기

N,M 조건을 보고는 모든 경우를 DFS로 탐색하는 방식을 사용했다.
좋은 해설을 보고 풀이를 업그레이드 시켰봤다.

1. 상하좌우 이동의 경우를 제한시켜 완전탐색의 경우의 수를 백만개에서 이천개로 줄이는 생각
   

2. ...RB 처럼 구슬이 인접해 있을 경우 R을 먼저 이동시켜야 정상적으로 B구슬까지 이동시킬 수 있다. 이 점을 고려하여 좌표값의 대소관계를 비교하여 구슬의 우선순위를 선택하는 방식으로 문제를 풀었다. 하지만 RBR 또는 BRB 이동을 사용하면 우선순위를 고려하지 않아도 된다.

# init
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', 'R', '.', '.', 'B', '.', '.', '.', '.', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']

# R 이동
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '.', '.', 'R', 'B', '.', '.', '.', '.', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']

# B 이동
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '.', '.', 'R', '.', '.', '.', '.', 'B', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']

# R 이동 -> 이 함수의 인자는 처음 R 이동으로 도착한 좌표를 사용해야한다.
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']
['#', '.', '.', '.', '.', '.', '.', 'R', 'B', '#']
['#', '#', '#', '#', '#', '#', '#', '#', '#', '#']

• REF: https://www.youtube.com/watch?v=SarTy3ZwmVo