from collections import deque
import sys
N, M = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [[False] * M for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(N): #그래프 만들기
line = list(map(int, list(sys.stdin.readline().rstrip())))
for j in range(M):
if line[j] == 1:
graph[i][j] = True
def bfs(x, y):
q = deque([(x, y)])
while q:
prev_x, prev_y = q.popleft()
for i in range(4):
next_x = prev_x + dx[i]
next_y = prev_y + dy[i]
if 0 <= next_x < N and 0 <= next_y < M:
if graph[next_x][next_y] == 1:
q.append((next_x, next_y))
graph[next_x][next_y] = graph[prev_x][prev_y] + 1
bfs(0, 0)
print(graph[N-1][M-1])
처음에 count
값을 선언하고 그걸로 값을 계산하다가 한계를 느껴 graph 자체의 값을 변경하는 것으로 바꿨다.
참고
from collections import deque
import sys
N, M = list(map(int, sys.stdin.readline().rstrip().split()))
graph = [list(map(int, ' '.join(sys.stdin.readline().rstrip().split()))) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs():
q = deque([(0, 0)])
while q:
prev_x, prev_y = q.popleft()
for i in range(4):
next_x, next_y = prev_x + dx[i], prev_y + dy[i]
if 0 <= next_x < N and 0 <= next_y < M:
if graph[next_x][next_y] == 1:
q.append((next_x, next_y))
graph[next_x][next_y] = graph[prev_x][prev_y] + 1
bfs()
print(graph[N-1][M-1])
위 블로그 글을 공부한 다음 안보고 풀어봤다.
2번 푸니까 예전에 공부했떤 BFS가 떠오른다