https://www.acmicpc.net/problem/2178
그래프의 탐색을 활용하는 문제다. 깊이 우선 탐색(DFS)는 경로가 여러개 존재할 경우 모든 경로를 완전 탐색하고 그 중에서 최솟값을 찾는다. 따라서 시간이 굉장히 오래 걸리는 데에 비해 너비 우선 탐색(BFS)는 항상 최단 경로를 보장한다. 해당 문제는 경로의 특징에 영향을 받지 않고, 최단 경로만을 구하면 되기 때문에 BFS로 풀이하는 것이 적합하다.
collections
모듈의 deque
객체에 삽입하고, step
배열의 시작점을 1로 초기화한다.deque
내부에 값이 존재하는 동안 popleft()
메서드를 사용하여 왼쪽에서부터 좌표 정보를 가져온다.zip()
함수를 사용하여 방향 정보를 불러오고 다음으로 이동할 위치를 찾는다.deque
에 삽입한다.step
값을 이전 위치의 값 + 1로 설정한 뒤 다음 위치로 이동한다.step
값을 반환한다.from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(input().rstrip()))
step = [([0] * m) for _ in range(n)]
visited = [([0] * m) for _ in range(n)]
q = deque()
def bfs():
dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]
while q:
x, y = q.popleft()
for dx, dy in zip(dxs, dys):
nx, ny = x + dx, y + dy
if (0 <= nx < m) and (0 <= ny < n) and graph[ny][nx] == "1" and not visited[ny][nx]:
visited[ny][nx] = 1
q.append((nx, ny))
step[ny][nx] = step[y][x] + 1
q.append((0, 0))
step[0][0] = 1
bfs()
print(step[-1][-1])