[김태원 알고리즘] 알리바바와 40인의 도둑 (DP)

사용 언어: Python3

문제

풀이

내 풀이 - BFS

from collections import deque

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]

dist = [[0] * N for _ in range(N)]

q = deque()
q.append((0, 0))
dist[0][0] = lst[0][0]

dx, dy = [0,1], [1,0] # 오른쪽 혹은 아래쪽
while q:
    x, y = q.popleft()
    for w in range(2):
        xx, yy = x+dx[w], y+dy[w]
        if xx<0 or xx>=N or yy<0 or yy>=N:
            continue
        q.append((xx, yy))
        if dist[xx][yy] == 0: # 처음 방문하는 곳이면 바로 값 업데이트
            dist[xx][yy] = dist[x][y] + lst[xx][yy]
        else: # 두번째 방문하는 곳이면 더 기존값과 이번에 나온 값 중 최솟값으로 업데이트
            dist[xx][yy] = min(dist[xx][yy], dist[x][y] + lst[xx][yy])

print(dist[N-1][N-1])

• 실패
  • 1~5번 테스트 케이스 중 2번까지 간당간당하게 성공하고 3번부터 5번은 실패한다ㅜ

다른 풀이 - Bottom Up 🌟

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)] # (i, j)까지 드는 에너지의 최소량

# ✅ 확실한 것만 초기화 (0행 라인, 0열 라인)
dp[0][0] = board[0][0]
for i in range(1, N):
    dp[0][i] = dp[0][i-1] + board[0][i]
    dp[i][0] = dp[i-1][0] + board[i][0]

# 이제 dp 계산
for i in range(1, N):
    for j in range(1, N):
      # ✅ (i, j)까지 가는 방법은 (i-1, j)에서 오거나 (i, j-1)에서 오는 경우 두 가지밖에 없다
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + board[i][j]

print(dp[N-1][N-1])

다른 풀이 - Top Down

def DFS(x, y):
    if dp[x][y] != 0: # ✅ cut edge
        return dp[x][y]
    if x == 0 and y == 0:
        return board[0][0]
    else:
        if x == 0:
            dp[x][y] = DFS(0, y-1) + board[0][y] # ✅ 메모이제이션
        elif y == 0:
            dp[x][y] = DFS(x-1, 0) + board[x][0] # ✅ 메모이제이션
        else:
            dp[x][y] = min(DFS(x-1, y), DFS(x, y-1)) + board[x][y] # ✅ 메모이제이션
        return dp[x][y]

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]

print(DFS(N-1, N-1))

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기