미로에 물을 쏟아 최단 경로를 구해요. BFS 알고리즘 [코딩테스트 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

출력: [[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 LoadOfFlood(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],
        ]
path = LoadOfFlood(maze,1,1)
print(path)

솔루션

dx=[ 0,1,0,-1]
dy=[-1,0,1,0]
def BackTracking(maze,ex,ey):
    foots=[]
    foots.append([ex,ey])
    foot = maze[ey][ex]
    while(True):
        for di in range(0,4):
            x = ex + dx[di]
            y = ey + dy[di]
            if(maze[y][x] == foot-1):
                foots.append([x,y])
                ex = x
                ey = y
                foot = maze[y][x]
                break
        if(foot == 1):
            foots.reverse()
            return foots

def LoadOfFlood(maze,sx,sy):
    queue = []
    queue.append([sx,sy])
    foot = maze[sy][sx]
    while(len(queue)>0):        
        sx,sy = queue.pop(0)
        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
               return BackTracking(maze,x,y)               
           elif (maze[y][x]==0):
               maze[y][x]= foot+1
               queue.append([x,y])
    return []
    
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],
        ]
path = LoadOfFlood(maze,1,1)
print(path)

시뮬레이션 코드

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 BackTracking(maze,ex,ey):
    foots=[]
    foots.append([ex,ey])
    foot = maze[ey][ex]
    while(True):
        for di in range(0,4):
            x = ex + dx[di]
            y = ey + dy[di]
            if(maze[y][x] == foot-1):
                foots.append([x,y])
                ex = x
                ey = y
                foot = maze[y][x]
                break
        if(foot == 1):
            foots.reverse()
            return foots

def LoadOfFlood(maze,sx,sy):
    queue = []
    queue.append([sx,sy])
    foot = maze[sy][sx]
    while(len(queue)>0):        
        sx,sy = queue.pop(0)
        nfoot = maze[sy][sx]
        if(nfoot != foot):
            foot = nfoot
            DrawMaze(maze)
        for di in range(0,4):
           x = sx + dx[di]
           y = sy + dy[di]
           if(maze[y][x]==-2):
               maze[y][x]= foot+1
               return BackTracking(maze,x,y)               
           elif (maze[y][x]==0):
               maze[y][x]= foot+1
               queue.append([x,y])
    return []
    
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],
        ]
path = LoadOfFlood(maze,1,1)
print(path)