동민이는 NxM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러마리 괴물이 있어 이를 피해탈출해야 한다. 동빈이의 위치는 (1,1)이고, 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.
미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때, 동민이가 탈출하기 위해 움직여야하는 최소 칸의 개수는? 칸을 셀 때는 마지막 칸과 시작칸 모두 포함한다.
✅ 최소거리를 구하는 과정이라 BFS를 사용 → 도착시, 바로 종료가 가능해서 유리
🙄 문제 : 최소거리를 측정하는데 필요 없는 곳을 조사할 때, count를 하는 문제
from collections import deque
n, m = map(int, input().split())
maze = [[int(i[j])for j in range(m)] for i in [input() for _ in range(n)]]
queue = deque()
visited = [[False if i[j] == 1 else True for j in range(m)] for i in maze]
cnt = 1
dr = [0,1,-1,0]
dc = [1,0,0,-1]
# 시작 위치 방문 및 큐 삽입
queue.append((0,0))
visited[0][0] = True
# bfs 시작
while queue:
cur = queue.popleft()
r, c = cur[0], cur[1]
for i in range(len(dr)):
nr = r + dr[i]
nc = c + dc[i]
if nr < 0 or nr >= n or nc < 0 or nc >= m:
continue
if maze[nr][nc] == 1 and not visited[nr][nc]: # 1이거나 미방문이면
queue.append((nr,nc))
visited[nr][nc] = True
cnt += 1
print("이프문 들어간다 후",nr,nc, '->', cnt)
if nr == n-1 and nc == m-1: # 도착지에 도착하면 멈춤
break
if nr == n-1 and nc == m-1:
break
print("리얼현재",nr,nc, '->', cnt)
print(cnt)
🌳 BFS는 시작 지점에서 가까운 노드부터 차례로 그래프의 모든 노드를 탐색한다.
🌳 모든 노드의 거리가 1로 동일하므로 모든 노드의 최단 거리값을 기록하면 해결 가능
from collections import deque
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]
# 미로공간 벗어낫는가?
if nx < 0 or nx >= n or ny < 0 or ny >=m:
continue
# 괴물이 존재하는가?
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] # 마지막 위치까지의 최단 거리 반환
n, m = map(int, input().split())
graph = [[int(i[j])for j in range(m)] for i in [input() for _ in range(n)]]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
print(bfs(0,0))
🐾 그래프에 직접 최소거리 저장하는 스킬