[백준/Python] 2178번 미로탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

---

풀이

from collections import deque

'''
1이 이동할 수 있는 곳, 최단 거리를 알아내야 함! 
그러니 bfs로 풀어보자
(dfs로 접근하게 된다면 케이스끼리 visited 배열을 침해해서 안된다)
'''
steps=[[-1,0],[1,0],[0,-1],[0,1]] # 상 하 좌 우

n,m=map(int,input().split())
maze=[[] for _ in range(n)]
for i in range(n):
    maze[i]=list(map(int,input()))
    
def bfs(maze):
    queue=deque([[0,0]]) # 미로의 시작지점
    
    while (queue):
        
        y,x=queue.popleft()
        #큐가 비지 않을 때 까지
        
        for step in steps:
            
            nextY=y+step[0]
            nextX=x+step[1]
            if nextX<0 or nextY<0 or nextY>=n or nextX>=m: #인덱스가 범위 값 벗어남
                continue
            if maze[nextY][nextX]==0: # 이동 할 수 없는 칸 (0)
                continue
            if maze[nextY][nextX]==1: # 그 외의 경우(이동 가능)
                queue.append([nextY,nextX])
                maze[nextY][nextX]=maze[y][x]+1
    return maze[n-1][m-1]

print(bfs(maze))

bfs로 풀면 되는 문제다.
dfs로 풀기 위해서는 매번 visited를 바꿔 끼워야 하며, 맨 끝까지 도달할 수 있는 모든 케이스를 검사한 후 출력하기 때문에 시간 상으로도 비효율적이다.

BFS VS DFS

DFS

장점

• 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용합니다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS 보다 빠르게 찾을 수 있습니다.

단점

• 해가 없는 경로를 탐색 할 경우 단계가 끝날 때까지 탐색합니다. 효율성을 높이기 위해서 미리 지정한 임의 깊이까지만 탐색하고 해를 발견하지 못하면 빠져나와 다른 경로를 탐색하는 방법을 사용합니다.
• DFS를 통해서 얻어진 해가 최단 경로라는 보장이 없습니다. DFS는 해에 도착하면 탐색을 종료하기 때문입니다.

BFS

장점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다.

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

결론

1. 최단거리 => BFS
2. 이동할 때마다 가중치가 붙거나, 이동 과정에서 여러 제약이 있을 경우 DFS
3. 끝까지 탐색할 때, 특정 영역/깊이까지 가고 싶을 때 => DFS