해당 도착지로 가기 위해 지나야하는 최소의 칸 수를 구해야하므로 DFS, BFS 중에서 BFS로 풀어야겠다는 생각을 가져야 함
2차원 미로 배열 만들기
어떤 문자열에 list() 함수를 사용하면 해당 문자열은 리스트로 변환됨
변환된 리스트는 문자열이기 때문에 숫자로 변경해줘야 함
N × M 크기의 배열로 표현되는 미로이므로 for문의 range는 n
n, m = map(int, input().split()) # N × M 크기의 배열로 표현되는 미로, N개의 줄에 M개의 정수로 미로가 주어짐
maze = []
# 2차원 배열 만들기
for _ in range(n):
row = input()
row_list = list(row) # ['1', '0', '1', '0' ...]
int_list = list(map(int, row_list)) # [1, 0, 1, 0 ...]
maze.append(int_list)
미로에서 상, 하, 좌, 우로 움직여야하는 경우의 수 세팅
(1, 1)에서 위로 움직인다면? : (0, 1) => x축은 유지하고 y축에서 +1을 해야 함 dx = 0, dy = 1
# 상하좌우 방향
# x축과 y축을 움직이는 조합 : 왼쪽으로 움직이는 경우, 오른쪽으로 움직이는 경우, 아래로 가는 경우, 위로 가는 경우
# delta x : x 축 방향으로의 변화량
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
정답
from collections import deque
n, m = map(int, input().split()) # N × M 크기의 배열로 표현되는 미로, N개의 줄에 M개의 정수로 미로가 주어짐
maze = []
# 2차원 배열 만들기
for _ in range(n):
row = input()
row_list = list(row) # ['1', '0', '1', '0' ...]
int_list = list(map(int, row_list)) # [1, 0, 1, 0 ...]
maze.append(int_list)
# 상하좌우 방향
# x축과 y축을 움직이는 조합 : 왼쪽으로 움직이는 경우, 오른쪽으로 움직이는 경우, 아래로 가는 경우, 위로 가는 경우
# delta x : x 축 방향으로의 변화량
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def BFS(x, y):
queue = deque()
queue.append((x, y)) # 시작은 0,0
while queue:
x, y = queue.popleft()
# 시작 좌표에서부터 상, 하, 좌, 우로 움직이는 경우
for i in range(4):
# next x : 다음 x 좌표, 한칸 이동한 좌표
nx = x + dx[i]
ny = y + dy[i]
# 범위 벗어나면 skip
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
# 이동할 수 없는 칸이면 skip
if maze[nx][ny] == 0:
continue
# 처음 방문하는 길이면 현재까지의 거리 + 1
if maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1
queue.append((nx, ny))
return maze[n-1][m-1]
print(BFS(0, 0))
