시나리오
언휴는 나노 로봇으로 미로의 최단 경로를 찾는 실험을 하고 있어요.
미로에 나노 로봇을 포함한 물을 충분히 쏟아 붓는 거죠.
출구에 처음 도착한 나노 로봇이 온 길을 역 추적하면 최단 경로가 나올 거 같아요.
문제
난이도: 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)