[백준][파이썬] 2178 미로탈출 (최단거리)

처음에는 DFS문제라고 생각했다.

미로를 찾아가면서 결국 (M,N)에 도착한 값들을 list에 넣어주고 정렬시켜준다음에 최소값을 찾으면 되니까!!

결과는 잘 나왔다. 하지만 시간초과가 났다.

 

이런 최단거리 문제를 푸는 방법은 BFS라고 한다. 

처음에 어떻게 하면 최단길을 찾을 수 있을지 고민했다. (왠지 동적프로그래밍에 더 가까워지는듯한....)

답은 생각보다 간단했다.

모든 블록에 값을 넣어주는것..(수학 문제풀떄랑 비슷했다.)

 

사용한 리스트가 꽤 많았다.

visited -  방문여부 파악을 위해 사용

lit - 기존의 정보가 담겨있는 리스트

추가로 거리를 담아주는 리스트가 사용되었다.

dlog- 흔적을 남기는 배열이다.

 

DFS는 주로 재귀함수와 스택을

BFS는 주로 while문과 큐를 사용한다.

n,m = map(int,input().split())
lit = []
dlog = [[0 for i in range(m)] for j in range(n)]
visited = [[False for _ in range(m)] for __ in range(n)]
for i in range(n):
    t = input()
    t = list(t)
    lit.append(t)
dx =[0,0,1,-1]
dy =[1,-1,0,0]
ans =[]
def bfs(x,y,lit,n,m,count):
    stack = [[x,y]]
    dlog[0][0] = count
    while stack:
        x = stack[0][0]
        y = stack[0][1]
        del stack[0]
        for i in range(4):
            X=x+dx[i]
            Y=y+dy[i]
            if 0<=X<n and 0<=Y<m:
                if visited[X][Y] == False and lit[X][Y] =='1':
                    visited[X][Y] = True
                    dlog[X][Y] = dlog[x][y] + 1
                    stack.append([X,Y])

bfs(0,0,lit,n,m,1)
print(dlog[n-1][m-1])