[백준] 2178번(python 파이썬)

https://www.acmicpc.net/problem/2178

 

---

미로 문제

즉, 최단거리 문제는 BFS를 사용하여 해결할 수 있다. 현재 위치에서 가장 가까운 점을 먼저 방문하기 때문이다.

 

BFS

BFS는 큐를 이용하여 문제를 풀 수 있다.

1. 시작 좌표(0,0)를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 좌표를 꺼내 해당 좌표의 인접 좌표(상, 하, 좌, 우)중 방문하지 않고, 해당 좌표의 값이 0이 아닌 경우 좌표를 모두 큐에 삽입하고 방문처리를 한다. 해당 좌표의 값을 이전 좌표의 값 +1 로 증가 시킨다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

답 : n, m의 좌표에 있는 값 (해당 풀이에선 0부터 시작함으로 n-1, m-1이다.)

 

---

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def Bfs(cur_x, cur_y, graph, visited):
    queue = deque()
    queue.append((cur_x, cur_y))
    visited[cur_x][cur_y] = True

    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            next_x = pop_x + dx[i]
            next_y = pop_y + dy[i]
            if next_x <= -1 or next_x >= n or next_y <= -1 or next_y >= m:
                continue
            if not visited[next_x][next_y] and graph[next_x][next_y] != 0:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = True
                graph[next_x][next_y] = graph[pop_x][pop_y] + 1

Bfs(0, 0, graph, visited)

print(graph[n-1][m-1])