출처

전북대학교 리트머스 과제 ( 이경수 교수님 알고리즘 과제)

문제

입력 및 출력

입력 예제

4 4
6 7 12 5
5 3 11 18
7 17 3 3
8 10 14 9

출력 예제

40

접근

해당 문제를 처음 봤을 때 딱 떠 오른 문제가 있다. 바로 이전에 bfs로 시작 점부터 끝점까지 탐색을 했었던 문제 ‘쩰리’ 문제였다.

• dfs로 탐색을 하면 해당 노드의 모든 경우의 수를 다 탐색을 하고 다른 노드로 탐색을 하기 때문에 시간 복잡도가 오래 걸릴 가능성이 높아 보였다.
• 오른쪽,아래 쪽으로만 이동이 가는하기에 dx,dy를 적절하게 이용하면 될 것 같았다.

하지만 이전의 쩰리 문제와 다른점은 ‘잡스가 학교에 빠르게 가기 위해서는 걸리는 시간의 합이 최소가 되어야 한다’라는 부분이 추가가 되었다는 것이었다.

• 이는 dp를 이용하면 좋지 않을까 하는 생각이 들어 바로 적용해 보기로 했다.

코드

from collections import deque

import sys

input = sys.stdin.readline

n,m = map(int,input().rstrip().rsplit())
INF = 1e9
#가장 왼쪽 좌표 1,1

#우리는 0,0 ~ 3,3으로 간다
road = []

dp = [[INF] * m for _ in range(n)]

#그래프 생성
for _ in range(n):
    road.append(list(map(int,input().rstrip().rsplit())))

dp[0][0] = road[n-1][m-1]

def bfs(graph,dp,n,m):
    #출발 0,0

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

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

    while q:
        cur_y,cur_x = q.popleft()

        #아래, 오른쪽 이동
        for i in range(2):
            next_y = dy[i] + cur_y
            next_x = dx[i] + cur_x

            #범위 확인
            if 0 <= next_y < n and 0 <= next_x < m:
                new_time = dp[cur_y][cur_x] + graph[cur_y][cur_x]

                if new_time < dp[next_y][next_x]:
                    dp[next_y][next_x] = new_time
                    q.append((next_y,next_x))

    return dp

result = bfs(road,dp,n,m)

print(result[n-1][m-1])

어려웠던 점

1. 방문처리의 유무

   • 처음 문제를 해결할때 bfs를 이용해 문제를 풀다보니 방문처리를 하여 탐색했던 노드를 탐색하지 않게 했다.
   • 하지만 생각해 보니 어떻게 dp에 저장된 값 보다 현재 루트의 탐색값이 작을 때 갱신을 해야하기 때문에 방문 처리 부분을 삭제하였다.

2. dp 배열의 의미 정의

   • dp[y][x]: ‘graph[y][x]를 방문하기 이전의 최솟 값’을 저장으로 정의를 했었다
   • 해당 정의로 dp를 사용하면 마지막 road[n-1][m-1]의 값을 따로 더 해줘야 하는 번거로움이 생겼었다.
   • dp[y][x]: ‘graph[y][x]를 방문했을때 최솟 값’으로 정의하여 문제를 해결하여 값을 따로 더 해주는 과정을 생략했다.