[구현] 백준 13459번: 구슬 탈출 / 골드 3

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

13459번: 구슬 탈출

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

import copy

x_lim, y_lim = map(int, input().split())

visited = [[[[False] * y_lim for _ in range(x_lim)] for _ in range(y_lim)] for _ in range(x_lim)]
graph = []
for i in range(x_lim):
    row = [x for x in input()]
    for j in range(len(row)):
        if row[j] == 'R':
            rx = i
            ry = j
        elif row[j] == 'B':
            bx = i
            by = j
    graph.append(row)

visited[rx][ry][bx][by] = True

dxdy = [[1, 0], [-1, 0], [0, -1], [0, 1]]

def dfs(dir, rx, ry, bx, by, count, temp_graph):
    if count > 10:
        return

    if dir == dxdy[0] and by == ry and bx > rx:
        order = ['B', 'R']
    elif dir == dxdy[1] and by == ry and bx < rx:
        order = ['B', 'R']
    elif dir == dxdy[2] and bx == rx and by < ry:
        order = ['B', 'R']
    elif dir == dxdy[3] and bx == rx and by > ry:
        order = ['B', 'R']
    else:
        order = ['R', 'B']

    if order[0] == 'R':
        positions = [[rx, ry], [bx, by]]
    else:
        positions = [[bx, by], [rx, ry]]

    goal = False

    new_positions = [[0, 0], [0, 0]]
    for i in range(2):
        color = order[i]
        x, y = positions[i][0], positions[i][1]
        while True:
            nx = x + dir[0]
            ny = y + dir[1]
            if temp_graph[nx][ny] == '.':
                temp_graph[x][y] = '.'
                temp_graph[nx][ny] = color
                x = nx
                y = ny
                continue
            elif temp_graph[nx][ny] == 'O':
                if color == 'B':
                    return
                else:
                    goal = True
                temp_graph[x][y] = '.'
                x = nx
                y = ny
                break
            else:
                break

        if color == 'R':
            new_positions[0] = [x, y]
        else:
            new_positions[1] = [x, y]

    rx2, ry2 = new_positions[0][0], new_positions[0][1]
    bx2, by2 = new_positions[1][0], new_positions[1][1]


    if goal:
        print(1)
        quit()
        return

    if [rx, ry] == [rx2, ry2] and [bx, by] == [bx2, by2]:  # all balls don't move
        return

    if visited[rx2][ry2][bx2][by2] == True:
        visited[rx2][ry2][bx2][by2] = False
        return

    for i in range(4):
        dfs(dxdy[i], rx2, ry2, bx2, by2, count + 1, copy.deepcopy(temp_graph))

for i in range(4):
    dfs(dxdy[i], rx, ry, bx, by, 1, copy.deepcopy(graph))

print(0)

풀긴했지만 시간도 오래걸렸고 성능도 별로여서

언젠간 다시 풀어봐야겠다..