[백준] 2178. 미로 탐색

 

📌문제

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

 

🎖️난이도

 

✔️풀이

# 정답 - bfs (visited, queue)
from collections import deque
n, m = map(int, input().split())
miro = [list(map(int, list(input()))) for _ in range(n)]

visited = [[0]*m for _ in range(n)] # ~까지의 이동 횟수(방문한 칸 수)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# bfs
q = deque()
q.append([0, 0]) # 시작 위치
visited[0][0] = 1 # 시작 위치까지의 방문 칸 수 1칸

# 큐가 빌 때까지 반복
while q: 
    x, y = q.popleft()
    if x == n-1 and y == m-1:
        print(visited[x][y])
        break
    for i in range(4):
        nx = x + dx[i] # -1 -> 1 ->  0 -> 0
        ny = y + dy[i] #  0 -> 0 -> -1 -> 1
        if 0 <= nx < n and 0 <= ny < m: # 범위 내 인덱스
            if miro[nx][ny] == 1 and visited[nx][ny] == 0:
                q.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1 #방문 칸수 1 추가