bfs로 풀이

인프런 커뮤니티 질문&답변

Minseok Jeong

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

7. 알리바바와 40인의 도둑(Bottom-Up)

작성

250

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 방식으로 풀었을 때 시간 복잡도의 큰 손해가 존재하는지 궁금합니다. 테스트케이스는 통과를 하였습니다.

코테 준비 같이 해요! python

퀴즈

71%나 틀려요. 한번 도전해보세요!

동적 계획법(Dynamic Programming)의 핵심 아이디어는 무엇일까요?

문제를 가능한 모든 경우를 탐색하여 최적해를 찾습니다.

현재 상태에서 가장 좋은 선택만을 따라갑니다.

큰 문제를 작은 부분 문제로 나누어 해결하고 그 해답을 재사용합니다.

데이터를 정렬하여 검색 성능을 최적화합니다.

답변 1