탐색 알고리즘 문제 풀이

문제 해결 tip

• BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하므로,
• 최단 거리 찾기 문제해결에 적합
• (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리값을 기록한다

from collections import deque

n, m = map(int, input().split())		# N과 M의 값을 공백을 기준으로 구분하여 입력 받는다
						# 2차원 리스트의 맵 정보 입력
graph = []
for i in range(n):
	graph.append(list(map(int, input())))
    
# x와 y축을 기반한 상하좌우 이동 방향 정의
direction_x = [-1, 1, 0, 0]
direction_y = [0, 0, -1, 1]

# BFS 구현
def bfs(x, y):
	queue = deque()
    queue.append((x, y))
    
    while queue:					# 큐가 빌 때까지 반복
		x, y = queue.popleft()
        for i in range(4):				# 현 위치에서 상하좌우 위치 확인
        	nx = x +direction_x[i]
            ny = y +direction_y[i]
            
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
            	continue				# 미로 공간(N x M) 벗어난 경우 무시
            if graph[nx][ny] == 0:
            	continue				# 미로 벽인 경우 무시
            if graph[nx][ny] == 1:
            	graph[nx][ny] = graph[x][y] + 1		# 처음 방문하는 노드일 경우 최단 거리 기록
                queue.append((nx, ny))
     return graph[n-1][m-1]				# 가장 오른쪽 아래까지의 최단 거리 반환