코딩
백준 2178. 미로 탐색 파이썬(PYTHON)
무는빼주세요
2020. 11. 16. 10:14
문제링크 : www.acmicpc.net/problem/2178
2178번: 미로 탐색
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
www.acmicpc.net
def solution(MAPS,N,M):
stack=list()
visitied=list()
stack.append((0,0,1))
visitied.append((0,0))
dx=[0,0,1,-1]
dy=[1,-1,0,0]
answer = list()
while stack:
x,y,count = stack.pop(0)
if (x,y) == (N-1,M-1):
answer.append(count)
for i in range(4):
mx = x+dx[i]; my = y + dy[i]
if 0<=mx<N and 0<=my<M and (mx,my) not in visitied:
if MAPS[mx][my]==1:
stack.append((mx,my,count+1))
visitied.append((mx,my))
return min(answer)
def main():
N, M = map(int,input().split())
MAPS = list()
for i in range(N):
line = list(map(int,list(input())))
MAPS.append(line)
print(solution(MAPS,N,M))
main()