[프로그래머스] 수레 움직이기

https://school.programmers.co.kr/learn/courses/30/lessons/250134

접근방법:
파란공, 빨간공 각각 도착지로 갈 수 있는 경로를 모두 구함
이후 2중 for문을 통해 각 경로를 비교하여 적합 판정 이후 answer값 갱신

from collections import deque

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
def moving(blue_sx, blue_sy, blue_ex, blue_ey, maze, n, m):
    q = deque()
    possible_lst = []
    val = blue_sx * m + blue_sy
    q.append((blue_sx, blue_sy, [val]))
    
    while q:
        x, y, visited = q.popleft()
        
        if x == blue_ex and y == blue_ey:
            possible_lst.append(visited)
            continue
        
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            
            if not (0 <= nx < n and 0 <= ny < m):
                continue
            temp = nx * m + ny
            if temp in visited or maze[nx][ny] == 5:
                continue
            
            q.append((nx, ny, visited + [temp]))
    
    return possible_lst

def ispossible(b, r, maze):
    b_idx = 0
    r_idx = 0
    while True:
    	## 공 두개가 엇갈리는 경우를 check tc 4번
        if b_idx < len(b) - 1 and r_idx < len(r) - 1:
            if b[b_idx] == r[r_idx + 1] and b[b_idx + 1] == r[r_idx]:
                return False
        ## 두 공의 현재 위치가 같으면 False 
        if b_idx == len(b) - 1 and r_idx == len(r) - 1:
            if b[b_idx] != r[r_idx]:
                return True
            
        if b[b_idx] == r[r_idx]:
            return False
        
        if b_idx < len(b) - 1:
            b_idx += 1
        
        if r_idx < len(r) - 1:
            r_idx += 1
        
        
    
def solution(maze):
    answer = 200
    n = len(maze)
    m = len(maze[0])
    blue_sx, blue_sy, red_sx, red_sy = -1, -1, -1, -1
    blue_ex, blue_ey, red_ex, red_ey = -1, -1, -1, -1
    for i in range(n):
        for j in range(m):
            if maze[i][j] == 1:
                red_sx, red_sy = i, j
            elif maze[i][j] == 2:
                blue_sx, blue_sy = i, j
            elif maze[i][j] == 3:
                red_ex, red_ey = i, j
            elif maze[i][j] == 4:
                blue_ex, blue_ey = i, j
            

    b_load = moving(blue_sx, blue_sy, blue_ex, blue_ey, maze, n, m)
    r_load = moving(red_sx, red_sy, red_ex, red_ey, maze, n, m)

    for b in b_load:
        for r in r_load:
            if ispossible(b, r, maze):
                answer = min(answer, max(len(b), len(r)) - 1)
    
    if answer == 200:
        answer = 0
    return answer