[백준] 1261 알고스팟 python

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

import sys; input = sys.stdin.readline
from collections import deque
M, N = map(int, input().rstrip().split())
matrix = [list(map(int, list(input().rstrip()))) for _ in range(N)]
visit = [[M + N] * M for _ in range(N)]
def bfs():
    q = deque()
    q.append((0, 0))
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    visit[0][0] = 0
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or nr >= N or nc < 0 or nc >= M: continue
            if visit[nr][nc] > visit[r][c] + matrix[r][c]:
                visit[nr][nc] = visit[r][c] + matrix[r][c]
                q.append((nr, nc))

bfs()
print(visit[N-1][M-1])

BFS로 조건을 마구마구 집어넣으니 시간초과가 걸렸다. 어떻게 할지 고민했는데 더이상 떠오르지 않아서 나현님의 코드를 참고했다. 

나현님의 코드는 BFS인데 벽을 통과할때는 1을 추가하면서 작은 값일때만 갱신하는 코드이다. 나도 이와 비슷하게 짰더니 통과

import sys; input = sys.stdin.readline
from heapq import heappop, heappush
M, N = map(int, input().rstrip().split())
matrix = [list(map(int, list(input().rstrip()))) for _ in range(N)]
visit = [[M + N] * M for _ in range(N)]
def bfs():
    q = [(0, 0, 0)]
    dr = [1, -1, 0, 0]
    dc = [0, 0, 1, -1]
    visit[0][0] = 0
    while q:
        w, r, c = heappop(q)
        if r == N and c == M: return
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if nr < 0 or nr >= N or nc < 0 or nc >= M: continue
            if visit[nr][nc] > visit[r][c] + matrix[r][c]:
                visit[nr][nc] = visit[r][c] + matrix[r][c]
                heappush(q, (visit[nr][nc], nr, nc))


bfs()
print(visit[N-1][M-1])

제출하고 보니 다익스트라와 같은 알고리즘이어서 heapq를 사용해서 다시한번 시도했다.

우선순위 큐가 확실히 조금더 빨랐다.

 

---

이런 기본적인 문제도 혼자 못풀다니...