[Python/Baekjoon] 2178. 미로 탐색

문제

1. 난이도: 백준 실버 1

2. 문제 요약:

• N*M 크기의 배열의 미로가 주어질 때, 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸을 의미한다.

• (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소한의 칸 의 수를 구하라

• 입력: 첫째 줄에 N, M(2<=N, M <=100)이 주어지고 다음 줄에는 M개의 정수로 미로가 주어진다.

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

• 입력 예시:
  4 6
  101111
  101010
  101011
  111011

• 출력 예씨:
  15

3. 문제핵심: BFS(최소의 칸 개수)

이상 코드

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            #x, y 범위에서 벗어나는 경우
            if nx<0 or nx>= n or ny<0 or ny>= m:
                continue
                
            #0(이동할 수 없는 칸)인 경우
            if graph[nx][ny] == 0:
                continue
                
            #방문한 적이 없고 0이 아닌 경우
            if graph[nx][ny] == 1: 
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
                
    return graph[n-1][m-1]

from collections import deque

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]

print(bfs(0,0))

배운 점

• visited 배열을 따로 만들 필요 없이 graph 2차 배열에 +1을 하는 방식으로 방문과 현재까지의 거리를 동시에 구할 수 있다.