[BOJ] 1261 / 알고스팟 / Python 파이썬

[BOJ] 1261 / 알고스팟 / Python 파이썬

[BOJ] 1261 / 알고스팟 / Python 파이썬

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

1261번: 알고스팟

 

 

풀이

누적 합이 가장 적은 구간을 찾는 문제이다.

 

처음에는 deque 를 이용한 bfs 로 구하였는데 시간초과가 발생 하였다.

 

어느 경우에서든 "누적 합" 이  적은 경우로 진행하여야 하기 때문에, 우선순위 queue 로 해결하여야 효율적으로 해결 할 수 있었다.

이를 위하여 deque 에서 appendleft 로 누적합이 적은 경우를 우선적으로 진행되도록 구현해주었다.

 

※ heapq 를 사용하여 해결 할 수도 있었다.

 

from collections import deque

N, M = map(int, input().split())

maps = []

for _ in range(M):
    maps.append(list(map(int, input())))

dy = [1, 0, 0, -1]
dx = [0, 1, -1, 0]

queue = deque()
queue.append((0, 0, 0))

visited = [[(M*N)+1 for _ in range(N)] for _ in range(M)]

res = (M*N) + 1

while queue:
    y, x, cnt = queue.popleft()

    if y == M-1 and x == N-1:
        res = min(res, cnt)
        continue

    for i in range(4):
        Y = y + dy[i]
        X = x + dx[i]

        if 0 <= Y < M and 0 <= X < N:
            if maps[Y][X] and cnt + 1 < visited[Y][X]:
                visited[Y][X] = cnt+1
                queue.append((Y, X, cnt + 1))
            elif not maps[Y][X] and cnt < visited[Y][X]:
                visited[Y][X] = cnt
                # queue.append((Y, X, cnt))
                queue.appendleft((Y, X, cnt))

print(res)

 

 

---

참고 블로그

https://vixxcode.tistory.com/35

1261번 알고스팟 백준 파이썬

 

https://pacific-ocean.tistory.com/284

[백준] 1261번(python 파이썬)