-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
bfs로 풀이
21.07.14 14:46 작성 조회수 157
0
import sys
from collections import deque
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
dp[0][0] = mat[0][0]
que = deque()
que.append((0, 0))
while que:
y, x = que.popleft()
for dy, dx in zip([0, 1], [1, 0]):
ny, nx = y+dy, x+dx
if 0 <= ny < n and 0 <= nx < n: # 범위 확인
if dp[y][x]+mat[ny][nx] < dp[ny][nx]: # 최소 에너지가 존재하는 경우
dp[ny][nx] = dp[y][x]+mat[ny][nx]
que.append((ny, nx))
elif not dp[ny][nx]: # 처음 초기화되어 있는 곳(0)
dp[ny][nx] = dp[y][x]+mat[ny][nx]
que.append((ny, nx))
print(dp[n-1][n-1])
이 문제를 bfs 방식으로 풀었을 때 시간 복잡도의 큰 손해가 존재하는지 궁금합니다. 테스트케이스는 통과를 하였습니다.
답변을 작성해보세요.
0
김태원
지식공유자2021.07.17
안녕하세요^^
이런 문제는 bottom-up 다이나믹으로 하시는게 좋습니다. 아무래도 다이나믹보다는 시간상의 손해가 있습니다. 하지만 위에 코드도 좋은 코드입니다.
답변 1