백준_실버1_2178번(미로 탐색)

이번 문제는 BFS의 전형적인 문제로 미로가 주워지고 맵이 주워졌을 때 시작점에서 도착지까지 최단 거리를 구하는 문제이다. 먼저 이러한 문제를 만났을 때, BFS와 DFS 모두 사용할 수 있지만 효율적으로 전체 노드를 탐지하지 않아도 되고 최단 거리를 구해야 함으로 BFS를 사용하는 것이 효과적이라 생각했다.
이러한 문제는 Map 리스트와 Visited 리스트를 만들어서 갈수 있는 곳과 없는 곳을 Map에 추가하고 방문횟수를 Visited리스트에 추가한다.
그리고 상하좌우로 이동할 경우 (BFS관점에서 특정 노드의 근접노드들이라고 생각하면 되겠다) 이전에 방문하지 않았고, 갈 수 있는 노드라면, 전 노드의 방문 횟수(이 문제에서는 Visited값)에 하나씩 더하는 꼴로 진행하면 될 것이다.

from collections import deque
n,m = map(int,input().split())
table = []
for i in range(n):
    table.append(list(input()))

def bfs(table):
    visited = [[-1 for _ in range(m)] for _ in range(n)]
    visited[0][0] = 1
    start_x,start_y = 0,0
    control_x = [1,-1,0,0]
    control_y = [0,0,-1,1]
    queue = deque([[start_x,start_y]])
    while queue:
        now_x,now_y = queue.popleft()
        for i in range(4):
            next_x,next_y = now_x+control_x[i],now_y+control_y[i]
            if -1<next_x<m and -1<next_y<n:
                if visited[next_y][next_x] < 0 and table[next_y][next_x] == '1':
                    visited[next_y][next_x] = visited[now_y][now_x] + 1
                    queue.append([next_x,next_y])
    print(visited[-1][-1])
bfs(table)