[백준] 2178 - 미로 탐색 (Python)

문제 출처:

acmicpc.net/problem/2178

2178번: 미로 탐색

문제 풀이 :

• 각 수들이 붙어서 입력으로 주어진다. 이 수들을 나눠서 평소에 쓰던 2차원 list로 바꾸는 작업을 해주었다.
• 이후 전형적인 bfs 방법을 사용하여 풀었다.
• 이경우는 step by step에 구분을 주고 기저사례가 나온 경우에 해당 step을 출력해야 한다.
  • 때문에 현재 stack과 현재 stack에서 나아갈 수 있는 곳을 판별한 후에 다시 stack에 넣어주는 것이 아니라 n_stack에 따로 넣어준 뒤에
  • stack을 모두 돌고나면 cnt을 1증가시키고 n_stack에 있는 걸 stack으로 옮기면서 다음 스텝을 시작하도록 작성했다.

n,m = map(int,input().split())

temp = [input() for _ in range(n)]
maps=[]
for i in range(n):
    temp2=[]
    for j in temp[i]:
        temp2.append(int(j))
    maps.append(temp2)

dn = [0,1,0,-1]
dm = [1,0,-1,0]

n_stack=[1]
stack = [(0,0)]
visited = [[0]*m for _ in range(n)]
visited[0][0]=1

cnt=0
while(n_stack):
    cnt+=1
    #print(stack,cnt)
    n_stack=[]
    while(stack):
        cur_n,cur_m = stack.pop()
        for i in range(4):
            n_n = cur_n + dn[i]
            n_m = cur_m + dm[i]
            if(n_n>=n or n_n<0 or n_m<0 or n_m >=m):
                continue
            if(n_n==n-1 and n_m == m-1):
                n_stack = []
                stack =[]
                print(cnt+1)
                break
            if(visited[n_n][n_m]==0 and maps[n_n][n_m]==1):
                visited[n_n][n_m]=1
                n_stack.append((n_n,n_m))
    stack=n_stack