미로에 갖힌 쥐, DFS 알고리즘 [코딩테스트 Python]

시나리오

언휴는 지난 밤에 악몽을 꿨어요.

꿈에서 언휴는 사람이 아닌 쥐였고 미로에 갖혔답니다.

언휴는 마킹을 하면서 미로를 이동했어요.

가다가 막히면 마킹한 것을 따라 갈림길까지 되돌아 오고 다시 가는 것을 반복했죠.

결국 언휴는 미로를 탈출했었요.

다음 날에도 언휴는 같은 미로에 갖히는 꿈을 꾸었죠.

지난 꿈에 마킹한 흔적이 있어서 좀 더 쉽게 미로를 탈출할 수 있었답니다.

문제

난이도: 3 (middle) [1:very easy, 2:easy, 3:middle, 4: difficult, 5: very difficult]

입력: [[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
[-1, 1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1],
[-1, 0,-1,-1, 0,-1, 0,-1, 0,-1, 0,-1],
[-1, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0,-1],
[-1, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1],
[-1, 0,-1, 0,-1,-1, 0,-1, 0,-1,-1,-1],
[-1, 0,-1,-1, 0,-1, 0, 0, 0, 0, 0,-1],
[-1, 0,-1, 0, 0,-1, 0,-1, 0,-1, 0,-1],
[-1, 0, 0, 0, 0,-1, 0,-1, 0,-1, 0,-1],
[-1, 0,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1],
[-1, 0, 0, 0,-1,-1,-1, 0, 0,-1,-2,-1],
[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],], 1, 1

출력: [[2,1],[3,1],[4,1],[4,2],[4,3],[4,4],[5,4],[6,4],[6,5],[6,6],[7,6],[8,6],[9,6],[10,6],[10,7],[10,8],[10,9],[10,10]]

코드

def FindLoad(maze,sx,sy):
    
maze = [
    [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
    [-1, 1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1],
    [-1, 0,-1,-1, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0,-1],
    [-1, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1],
    [-1, 0,-1, 0,-1,-1, 0,-1, 0,-1,-1,-1],
    [-1, 0,-1,-1, 0,-1, 0, 0, 0, 0, 0,-1],
    [-1, 0,-1, 0, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0, 0, 0, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1],
    [-1, 0, 0, 0,-1,-1,-1, 0, 0,-1,-2,-1],
    [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
        ]
print(FindLoad(maze,1,1))

솔루션

dx=[ 0,1,0,-1]
dy=[-1,0,1,0]
def GoRobotMouse(maze,sx,sy,foots):           
    foot = maze[sy][sx]    
    for di in range(0,4):
       x = sx + dx[di]
       y = sy + dy[di]
       if(maze[y][x]==-2):
           maze[y][x]=foot+1
           foots.append([x,y])
           return True
       if(maze[y][x]==0):
           maze[y][x] = foot+1
           if(GoRobotMouse(maze,x,y,foots)):
               foots.append([x,y])
               return True
def FindLoad(maze,sx,sy):
    foots=[]    
    GoRobotMouse(maze,sx,sy,foots)    
    foots.reverse()
    return foots 
    
maze = [
    [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
    [-1, 1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1],
    [-1, 0,-1,-1, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0,-1],
    [-1, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1],
    [-1, 0,-1, 0,-1,-1, 0,-1, 0,-1,-1,-1],
    [-1, 0,-1,-1, 0,-1, 0, 0, 0, 0, 0,-1],
    [-1, 0,-1, 0, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0, 0, 0, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1],
    [-1, 0, 0, 0,-1,-1,-1, 0, 0,-1,-2,-1],
    [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
        ]
print(FindLoad(maze,1,1))

시뮬레이션 코드

import os
import time
def DrawMaze(maze):
    os.system('cls')    
    for y in range(0,len(maze)):
        for x in range(0,len(maze[0])):
            if(maze[y][x]==-1):
                print("■",end='')
            elif(maze[y][x]==0):
                print("%2s"%" ",end='')
            else:
                print("%2d"%(maze[y][x]),end='')
        print()    
    time.sleep(0.5)

dx=[ 0,1,0,-1]
dy=[-1,0,1,0]
def GoRobotMouse(maze,sx,sy,foots):        
    DrawMaze(maze)        
    foot = maze[sy][sx]    
    for di in range(0,4):
       x = sx + dx[di]
       y = sy + dy[di]
       if(maze[y][x]==-2):
           maze[y][x]=foot+1
           foots.append([x,y])
           return True
       if(maze[y][x]==0):
           maze[y][x] = foot+1
           if(GoRobotMouse(maze,x,y,foots)):
               foots.append([x,y])
               return True
    return False
def FindLoad(maze,sx,sy):
    DrawMaze(maze)    
    foots=[]    
    GoRobotMouse(maze,sx,sy,foots)    
    DrawMaze(maze)
    foots.reverse()
    return foots 
    
maze = [
    [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
    [-1, 1, 0, 0, 0, 0,-1, 0, 0, 0, 0,-1],
    [-1, 0,-1,-1, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0,-1,-1, 0,-1, 0, 0, 0,-1, 0,-1],
    [-1, 0,-1, 0, 0, 0, 0,-1,-1, 0, 0,-1],
    [-1, 0,-1, 0,-1,-1, 0,-1, 0,-1,-1,-1],
    [-1, 0,-1,-1, 0,-1, 0, 0, 0, 0, 0,-1],
    [-1, 0,-1, 0, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0, 0, 0, 0,-1, 0,-1, 0,-1, 0,-1],
    [-1, 0,-1,-1,-1, 0, 0,-1, 0, 0, 0,-1],
    [-1, 0, 0, 0,-1,-1,-1, 0, 0,-1,-2,-1],
    [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],
        ]
print(FindLoad(maze,1,1))