미로탐색 - 2178

[Silver I] 미로 탐색 - 2178

문제 링크

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

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

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

입력

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

출력

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

풀이

먼저 예전에 BFS는 최단거리 일 때 풀어야 한다고 들은 적이 있어서 BFS로 시도를 계속 했지만 갑자기 드문 의문이 그럼 언제 DFS, BFS를 구분 해야하는 지…?

1. DFS
   • 검색 대상 그래프가 큰 경우(정점과 간선의 개수가 많은 경우)
   • 경로의 특징을 저장해둬야 하는 문제[ ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안되는 문제]
   • BFS는 경로의 특징을 가지지 못함
2. BFS
   • 미로찾기 등 최단거리를 구해야 할 경우
   • DFS는 처음으로 발견되는 해답이 최단거리 보장을 못함
   • BFS는 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫 번째로 찾아지는 해답이 곧 최단거리
3. 미로찾기 풀이 흐름
   • 미로의 정보를 담을 수 있는 graph list와 방문한 노드인지 check하는 visited list 선언
   • 상, 하, 좌, 우를 바꿔가며 루트를 탐색하기 위해 현재의 위치에서 상,하,좌,우를 조정할 dx, dy list 선언
   • bfs 탐색 시작 (deque 이용)
   • 현재위치에서 상, 하, 좌,우 이동하며 이동한 위치가 invalid한 영역이거나, 벽에 가로 막히거나, 방문한 위치라면 다른 방향을 탐색하도록함
   • 갈 수 있는 새로운 루투라면 이전에 방문 한 위치의 노드 값 + 1 즉 이동한 거리를 기록한 후 queue에 enqueue
   • 다음에 방문 할 위치를 dequeue하여 상,하,좌,우 탐색 반복

코드

from collections import deque

def bfs(x, y):

    # bfs 를 위한 deque
    queue = deque()
    # 처음 start 지점을 enqueue
    queue.append((x, y))
    # 처음 start 지점을 visited 처리 
    visited[0][0] = 1
    # queue가 비어 있지 않는 동안 반복 
    while queue:
        x, y = queue.popleft()
        # 상, 하, 좌, 우 이동
        for i in range(4):
            
            nx = x + dx[i]
            ny = y + dy[i]
            # 상,하,좌,우 이동한 값이 invalid한 영역에 있는지 check
            if nx >= N or nx < 0 or ny >= M or ny < 0:
                continue
            # 벽에 가로 막히는지 check
            if graph[nx][ny] == 0:
                continue
            # 이미 방문한 노드인지 check
            if visited[nx][ny] :
                continue
            # 갈 수 있는 길이라면 
            if graph[nx][ny] == 1:
                # 이전에 방문 한 노드의 값 + 1 즉 이동한 거리
                visited[nx][ny] = visited[x][y] + 1
                queue.append((nx, ny))

    
    return visited[N-1][M-1]


N, M = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

visited = [[0 for _ in range(M)] for _ in range(N)]

print(bfs(0, 0))