[Python]13460. 구슬 탈출 2

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

13460번: 구슬 탈출 2

---

 

어느 방향으로 기울이는가에 따라 queue에 Red와 Blue의 좌표를 초기화 해주어야 한다.(중요!)

또한 현재 Red 와 Blue의 좌표를 계속 visited에 넣어주어서 이미 방문한 좌표에서의 재귀호출은 하지 않는다.

 

1. 최초의 Red, Blue 좌표를 매개변수로 recur() 호출
2. 현재의 Red, Blue 좌표를 가지고 4가지 방향으로 기울이면서 방문한 적이 없는 좌표로만 움직임
3. recur() 함수의 result 매개변수가 True일 때 빨간공만 탈출한 것이다. 이때의 depth로 최소값 없데이트한다.

 

from copy import deepcopy
 
def move_dir(MAP, red, blue, flag):
    global n, m
    queue = []
    if flag == 0:
        if red[0] < blue[0]:
            queue = [red, blue]
        else:
            queue = [blue, red]
    elif flag == 1:
        if red[0] > blue[0]:
            queue = [red, blue]
        else:
            queue = [blue, red]
    elif flag == 2:
        if red[1] < blue[1]:
            queue = [red, blue]
        else:
            queue = [blue, red]
    elif flag == 3:
        if red[1] > blue[1]:
            queue = [red, blue]
        else:
            queue = [blue, red]
 
    next_balls = {'R': None, 'B': None}
 
    while queue:
        r, c = queue.pop(0)
        if MAP[r][c] == 'R':
            opposite = 'B'
        else:
            opposite = 'R'
        isColorOut = False
        while True:
            n_r = r + d[flag][0]
            n_c = c + d[flag][1]
            if 0 <= n_r < n and 0 <= n_c < m:
                if MAP[n_r][n_c] == '#' or MAP[n_r][n_c] == opposite:
                    break
                elif MAP[n_r][n_c] == '.':
                    MAP[n_r][n_c], MAP[r][c] = MAP[r][c], MAP[n_r][n_c]
                elif MAP[n_r][n_c] == 'O':
                    isColorOut = True
                    MAP[r][c] = '.'
                    r, c = n_r, n_c
                    break
                r, c = n_r, n_c
        next_balls[MAP[r][c]] = [isColorOut, (r,c)]
    return next_balls
 
def tilt(MAP_origin, flag, red, blue):
    MAP = deepcopy(MAP_origin)
    next_balls = move_dir(MAP, red, blue, flag)
    if next_balls['R'] is None:
        isRedOut, (r_r, r_c) = next_balls['O']
    else:
        isRedOut, (r_r, r_c) = next_balls['R']
    if next_balls['B'] is None:
        isBlueOut, (b_r, b_c) = next_balls['O']
    else:
        isBlueOut, (b_r, b_c) = next_balls['B']
    if not isBlueOut and isRedOut:
        return True, MAP, (r_r, r_c), (b_r, b_c)
    else:
        return False, MAP, (r_r, r_c), (b_r, b_c)
 
def recur(depth, result, MAP, red, blue):
    global answer, n, m
    if depth > 10 :
        return
    if depth <= 10 and result:
        answer = min(answer, depth)
        return
    for i in range(4):
        _result, tilted_MAP, new_red, new_blue = tilt(MAP, i, red, blue)
        if (new_red, new_blue) not in visited:
            visited.append((new_red, new_blue))
            recur(depth+1, _result, tilted_MAP, new_red, new_blue)
            visited.pop()
 
 
n, m = map(int, input().split())
MAP = [list(input()) for _ in range(n)]
d = ((-1,0), (1,0), (0,-1), (0,1))
answer = 9876543210
 
for r in range(n):
    for c in range(m):
        if MAP[r][c] == 'R':
            red = (r,c)
        elif MAP[r][c] == 'B':
            blue = (r,c)
 
visited = [(red, blue)]
recur(0, False, MAP, red, blue)
if answer == 9876543210:
    answer = -1
print(answer)