2021.06.21
N * M 크기의 직사각형 형태의 미로
현재 위치 (1, 1)
출구는 (N, M)
괴물이 있는 부분 0 , 없는 부분 1
탈출하기 위한 최소 칸 수
이번에도 못 풀고 답안 예시를 보고 공부했다.
그런데 답안 예시대로 풀고 실행시켜보니 답이 틀리게 나온다,,
어디서 틀렸는지 찾아야하는데 못 찾고 있다.
# 미로 크기
n, m = map(int, input().split())
# 미로 형태
shape = []
for i in range(n):
shape.append(list(map(int, input())))
# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
from collections import deque
# BFS 메서드 정의
def bfs(x,y):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
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 ny < 0 or nx >= n or ny >= m:
continue
# 벽인 경우 무시
if shape[nx][ny] == 0:
continue
# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if shape[nx][ny] == 1:
shape[nx][ny] = shape[x][y] + 1
queue.append((nx,ny))
# 가장 오른쪽 아래까지의 최단 거리 반환
return shape[n-1][m-1]
print(bfs(0,0))
와,, 진짜 겨우 찾았다.
shape[nx][ny] = shape[x][y] + 1
여기에 ==을 썼었다;
아직 책 초반부인데 벌써부터 너무 어려운거같다,,,,,,,,큰일났다,,,,,