[백준 #2178 파이썬] 미로 탐색

2178번: 미로 탐색

 

DFS로는 시간초과가 나는 이유 : 전체 탐색

 

문제를 보면 처음에는 이건 무조건 그래프 탐색이다 라는 감이 됩니다.

다만, dfs로 풀지, bfs로 풀 지 고민을 하게 됩니다.

체감상 bfs로 푸는 게 조금 더 쉬운 느낌이 드는데, 사실 명확한 이유가 있습니다.

dfs 방식으로 푼다면, 모든 노드를 탐색해야 하는 결과가 나타날 수 있습니다.

그러한 방식으로 탐색을 하면 결과를 확인할 수 는 있지만, 최단거리임을 확인하기 위해서 더 많은 연산이 필요합니다.

따라서 이 경우에는 bfs를 통해 가장 짧은 거리의 결과를 얻는 것으로 결과를 얻을 수 있는 방식이 더욱 효율적입니다.

저도 이번에 bfs와 dfs 활용 목적을 알고 알고리즘을 풀어야 한다는 사실을 더 명확하게 배우게 되었습니다!

 

우선 bfs 풀이!

그래프 탐색에서 가장 중요하게 보아야 할 문제는 진행방향, 현재 위치, 나아갈 위치를 어떻게 구현할 지 고민하는 과정이 중요하다고 생각합니다. 

1. 그래서 일단 처음 내가 어느 위치에 있는지 등록할 필요가 있다고 생각해 현재 위치를 큐에 넣어줍니다.

2. 그리고 동서남북을 진행하면 되겠죠? n_x, n_y에 진행 방향을 만들어 줍니다!

(변수 명을 더 괜찮은 걸로 할걸 하는 생각이..)

3. 중요한 조건! 그래프의 범위를 벗어나면 안되고, 0을 만나면 다음 위치로 설정을 하면 안되므로 이 조건에 대한 처리를 해줍니다.

4. 1을 만나면 나는 여기를 나아갈 위치로 설정을 했으니 칸수의 진해으로 +1을 해주고 그 위치를 큐에 넣어줍니다.

(cnt변수를 만들어서 처리를 해주어도 되겠죠!)

5. while문을 통해서 큐가 없어질 때까지 이 과정을 반복하도록 하면 되겠죠!

6. 그 결과 마지막에 도착한 값만 retuern하도록 해주면 끝!

 

코드 결과

from collections import deque

n,m = map(int, input().split())
miro = []

for _ in range(n):
  miro.append(list(map(int, input())))

def bfs(x,y):
    n_x = [0,1,-1,0]
    n_y = [1,0,0,-1]

    queue = deque()
    queue.append((x,y))

    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx = x + n_x[i]
            ny = y + n_y[i]

            if nx>= n or ny>=m or nx < 0 or ny <0:
                continue         
            
            if miro[nx][ny] == 0:
                continue

            if miro[nx][ny] == 1:
                miro[nx][ny] = miro[x][y] + 1
                queue.append((nx,ny))

    return miro[n-1][m-1]

print(bfs(0,0))