[BOJ] 출근 - 13903 (S1)

시간 제한	메모리 제한
2 초	512 MB

문제

격자판 위에서 특정 이동 규칙에 따라 첫 번째 행에서 마지막 행까지 이동하는 최소 횟수를 구하는 문제이다.

풀이

BFS를 사용하여 최단 경로를 구한다.

코드

from collections import deque

R, C = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(R)]

N = int(input())
dxy = [list(map(int, input().split())) for _ in range(N)]

visited = [[False] * C for _ in range(R)]

q = deque()
for i, floor in enumerate(grid[0]):
    if floor == 1:
        q.append([0, i, 0])
        visited[0][i] = True

result = -1
while q:
    x, y, t = q.popleft()
    
    if x == R - 1:
        result = t
        break
    
    for dx, dy in dxy:
        nx, ny = x + dx, y + dy
        if not(0 <= nx < R and 0 <= ny < C):
            continue
        if grid[nx][ny] == 0 or visited[nx][ny]:
            continue
        
        q.append([nx, ny, t + 1])
        visited[nx][ny] = True

print(result)

시간 복잡도

O(R × C × N)