[프로그래머스] 블록 이동하기

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

bfs 심화버전
두블록이 이동하는 만큼 두 블록을 기준으로 방문처리 및
line out error를 신경썼음

from collections import deque, defaultdict

    
def solution(board):
    answer = 1e9
    n = len(board)
    
    q = deque()
    q.append((0, 1, 0))
    INF = 1e9
    dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
    
    def ispossible(a, b, c, d):
        if not (0 <= a < n and 0 <= b < n):
            return False

        if not (0 <= c < n and 0 <= d < n):
            return False
        
        if board[a][b] == 1 or board[c][d] == 1:
            return False
        
        return True
    
    distance = defaultdict(lambda: INF)
    distance[(0, 1)] = 0

    
    while q:
        s, e, cnt = q.popleft()
        sx, sy = s // n, s % n
        ex, ey = e // n, e % n

        if e == n*n - 1 or s == n*n - 1:
            # answer = min(answer, cnt)
            return cnt
            
        for k in range(4):
            na = sx + dx[k]
            nb = sy + dy[k]
            nc = ex + dx[k]
            nd = ey + dy[k]
            if not ispossible(na, nb, nc, nd):
                continue
            
            temp1, temp2 = na * n + nb, nc * n + nd
            
            ## TC 6번만 계속 틀렸는데 다익스트라 중 
            ## 동일 거리도 무시하지않고 체크해야함
            if distance[(temp1, temp2)] < cnt + 1:
                continue
            distance[(temp1, temp2)] = cnt + 1
            q.append((temp1, temp2, cnt + 1))
            

                
            if k == 0 and abs(s-e) == n:
                if distance[(s, s+1)] > cnt + 1:
                    distance[(s, s+1)] = cnt + 1
                    q.append((s, s+1, cnt + 1))
                
                if distance[(e, e+1)] > cnt + 1:
                    distance[(e, e+1)] = cnt + 1
                    q.append((e, e+1, cnt + 1))
                    
            if k == 1 and abs(s - e) == 1:
                if distance[(s, s+n)] > cnt + 1:
                    distance[(s, s+n)] = cnt + 1
                    q.append((s, s+n, cnt + 1))
                
                if distance[(e, e+n)] > cnt + 1:
                    distance[(e, e+n)] = cnt + 1
                    q.append((e, e+n, cnt + 1))
                    
            if k == 2 and abs(s - e) == n:
                if distance[(s-1, s)] > cnt + 1:
                    distance[(s-1, s)] = cnt + 1
                    q.append((s-1, s, cnt + 1))
                
                if distance[(e-1, e)] > cnt + 1:
                    distance[(e-1, e)] = cnt + 1
                    q.append((e-1, e, cnt + 1))
                    
            if k == 3 and abs(s - e) == 1:
                if distance[(s-n, s)] > cnt + 1:
                    distance[(s-n, s)] = cnt + 1
                    q.append((s-n, s, cnt + 1))
                
                if distance[(e-n, e)] > cnt + 1:
                    distance[(e-n, e)] = cnt + 1
                    q.append((e-n, e, cnt + 1))   
                
                
    return answer