[PCCP 기출문제] 4번 / 수레 움직이기 (python)

import sys
from collections import deque

dirs = [(0, 1), (1, 0), (-1, 0), (0, -1)]
board = []
red,blue=[],[]
N,M=0,0
answer=sys.maxsize
visit=[]
# 백트래킹
def dfs(red,blue,count):
    global answer
    #종료지점 도착했는지
    if board[red[0]][red[1]]==3 and board[blue[0]][blue[1]]==4: answer=min(answer,count)

    # 파란 수레가 이미 도착했다면
    if board[blue[0]][blue[1]]==4:
        for i in range(4):
            rnr,rnc=red[0]+dirs[i][0],red[1]+dirs[i][1]
            if rnr<0 or rnr>=N or rnc<0 or rnc>=M: continue
            if visit[rnr][rnc][0]: continue
            if board[rnr][rnc]==5: continue
            if rnr==blue[0] and rnc==blue[1]: continue
            visit[rnr][rnc][0]=1
            dfs([rnr,rnc],blue,count+1)
            visit[rnr][rnc][0]=0
    # 빨강 수레가 이미 도착했다면
    elif board[red[0]][red[1]]==3:
        for i in range(4):
            bnr,bnc=blue[0]+dirs[i][0],blue[1]+dirs[i][1]
            if bnr<0 or bnr>=N or bnc<0 or bnc>=M: continue
            if visit[bnr][bnc][1]: continue
            if board[bnr][bnc]==5: continue
            if bnr==red[0] and bnc==red[1]: continue
            visit[bnr][bnc][1]=1
            dfs(red,[bnr,bnc],count+1)
            visit[bnr][bnc][1]=0
    else:
        for i in range(4): # BLUE 먼저
            br,bc=blue[0]+dirs[i][0],blue[1]+dirs[i][1]
            if br < 0 or br >= N or bc < 0 or bc >= M: continue
            if visit[br][bc][1]: continue
            if board[br][bc]==5: continue
            for j in range(4): # RED 다음
                rr, rc = red[0] + dirs[j][0], red[1] + dirs[j][1]
                if rr < 0 or rr >= N or rc < 0 or rc >= M: continue
                if visit[rr][rc][0]: continue
                if board[rr][rc] == 5: continue
                if blue[0]==rr and blue[1]==rc and red[0]==br and red[1]==bc: continue # 서로 순서 바꿔치기 X
                if rr == br and rc == bc: continue # 같은 자리 X
                visit[rr][rc][0] = 1
                visit[br][bc][1] = 1
                dfs([rr,rc], [br, bc], count + 1)
                visit[rr][rc][0] = 0
                visit[br][bc][1] = 0
def solution(maze):
    global board
    global red,blue
    global N, M
    global visit
    global answer

    N, M = len(maze), len(maze[0])
    visit=[[[0]*2 for _ in range(M)] for _ in range(N)]
    board = maze[:]

	# 시작 지점 찾기
    for r in range(N):
        for c in range(M):
            if maze[r][c]==1:
                red=[r,c]
                visit[r][c][0]=1
            elif maze[r][c]==2:
                blue=[r,c]
                visit[r][c][1]=1
    dfs(red,blue,0)
    
    if answer==sys.maxsize: answer=0

    return answer