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

안녕하세요. 강사님. 강의 잘 보고 있습니다.

저도 다른 분을과 비슷하게 처음에 BFS로 문제를 풀었습니다.

확실히 DP로 푼 강사님의 코드가 훨씬 간결하긴한데 DP가 BFS보다 얼마나 효율적인지 잘 감이 잡히지 않습니다.

각각 어떤 시간복잡도를 갖는지 궁금합니다. 감사합니다!

# BFS 풀이
from collections import deque

N = int(input())
valley = [list(map(int, input().split())) for _ in range(N)]
dx = [1, 0]
dy = [0, 1]

def bfs(x, y):
    q = deque()
    q.append([x, y])
    visted = [[int(1e9)] * N for _ in range(N)]
    visted[x][y] = valley[x][y]

    while q:
        x, y = q.popleft()
        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]

            # 맵을 벗어나면 continue
            if nx >= N or ny >= N:
                continue

            # visted 표기 더 작은 경우에만
            if visted[nx][ny] > valley[nx][ny] + visted[x][y]:
                visted[nx][ny] = valley[nx][ny] + visted[x][y]
            
            q.append([nx, ny])
    
    return visted[N - 1][N - 1] 

print(bfs(0, 0))