[백준] Python 2178번 미로 탐색 실버1 - 그래프

문제 : https://www.acmicpc.net/problem/2178
분류 : 그래프, 너비 우선 탐색(BFS)

접근

1. 1인 곳만 밟으며 최단 거리를 구하면 된다.
2. 1에 인접한 곳들을 모두 Q에 넣으며 가중치를 증가시켜준다.

• https://www.youtube.com/watch?v=dzgmLJaTlBo
  이해가 안 됐었는데 이 영상 보고 바로 이해가 됐다. 3분10초까지만 보면 됨.

슈도코드

0,0에서 BFS 시작

BFS():
	Q에 시작노드 삽입
    
    while queue:
    	현재 위치 = q에서 pop
        현재 위치 방문 처리
        
        for 동서남북:
        	벗어나지 않는 선에서
            	이동하는 곳이 1이고 방문한 적이 없으면
                	이동하는 곳 방문처리
                    가중치 증가
                    Q에 삽입

마지막 위치에 최단 거리가 저장되어 있다.
          

풀이

from collections import deque

def solution():
    N, M = map(int, input().split())
    graph = []
    for _ in range(N):
        graph.append(list(map(int, input())))
    visited = [[False for j in range(M)] for i in range(N)]
    print(BFS(0, 0, graph, visited, N, M)
)

def BFS(i, j, graph, visited, N, M):
    # 큐 생성
    queue = deque()
    # 동 서 남 북
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    # 시작 노드 큐에 삽입
    queue.append((i, j))

    # 큐가 빌 떄 까지
    while queue:
        # 현재 y, x 큐에서 꺼냄
        cur_y, cur_x = queue.popleft()
        # 방문 처리
        visited[i][j] = True

        for k in range(4):
            # 동 서 남 북 으로 이동
            next_y = cur_y + dy[k]
            next_x = cur_x + dx[k]

            # 밖으로 나가지 않고 N,M보다 크지 않을 때
            if next_y >= 0 and next_x >= 0 and next_y < N and next_x < M:
                # 해당 값이 0이 아니고 방문하지 않았을 때
                if graph[next_y][next_x] != 0 and visited[next_y][next_x] == 0:
                    # 방문 처리
                    visited[next_y][next_x] = True
                    # 인접한 노드는 가중치 증가
                    graph[next_y][next_x] = graph[cur_y][cur_x] + 1
                    queue.append((next_y, next_x))
    return graph[N-1][M-1]
solution()