녹색 옷 입은 애가 젤다지?

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

문제요약:

2차원의 크기n이 주어지고 2차원 배열이 주어진다. 왼쪽위부터 0,0이라고 할때 0,0부터 n-1,n-1 까지 가는 길에 있는 경로의 값의 합중 가장 작은 값을 출력하라.

 

난이도:

골드4

 

소요시간:

45분 +15분

 

제출횟수:

2회

 

1차 코딩:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e6))

dy = [-1,0,1,0]
dx = [0,1,0,-1]
INF = int(125*125*9)
k = 0
while True:
    k+=1
    n = int(input())
    if n == 0:
        break
    
    arr = [list(map(int,input().split())) for _ in range(n)]
    m = INF
    min_visited= [[INF]*n for _ in range(n)]
    
    def dfs(y,x,S,visited):
        global m
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0<=ny<n and 0<=nx<n and (ny,nx) not in visited:
                if min_visited[ny][nx]<=S+arr[ny][nx]:
                    #다른번에 여기 온적이 있는데 지금이 더 큼
                    continue
                else:
                    min_visited[ny][nx] =S+arr[ny][nx]
                if ny==n-1 and nx==n-1 :
                    m = min(m,S+arr[-1][-1])
                else:
                    dfs(ny,nx,S+arr[ny][nx],visited|{(ny,nx)})
                        
    dfs(0,0,arr[0][0],set([]))
    print('Problem ',k ,': ',m,sep = '')

먼저 DFS로 푼 풀이 입니다. 풀면서도 이거 시간초과 나겠다라고 생각하면서 풀었는데(다른 풀이가 생각 안났음) 

모든 경우의 수를 전부 돌기 때문에 기하급수 적으로 늘어나며, 만약 두번째 이상 방문했는데 이전에 이길을 더 짧게 지나간적이 있으면 넘어가는 방향으로 시간복잡도를 줄여보고자 했었으나 역부족이었습니다. 후에 다익스트라로 푼다는 힌트를 본뒤 다시 풀었습니다.

 

2차 코딩:

import sys
input = sys.stdin.readline
import heapq as hp

dy = [-1,0,1,0]
dx = [0,1,0,-1]
INF = int(1e8)
k = 0
while True:
    k+=1
    n = int(input())
    if n==0:
        break

    arr = [list(map(int,input().split())) for _ in range(n)]
    def dikjstra():
        q = [(arr[0][0],0,0)]
        distance = [[INF]*n for _ in range(n)]
        distance[0][0] = arr[0][0]

        while q:
            dist,y,x = hp.heappop(q)
            if y == n-1 and x == n-1:
                break
            if dist > distance[y][x]:
                continue
            for i in range(4):
                ny = y+dy[i]
                nx = x+dx[i]
                if 0<=ny<n and 0<=nx<n:
                    cost = dist + arr[ny][nx]
                    if distance[ny][nx] > cost:
                        distance[ny][nx] = cost
                        hp.heappush(q,[cost,ny,nx])
        return dist

    print('Problem ',k,': ',dikjstra(),sep = '')

이전에 풀었던 코드는 두번째 반복부터는 계산해서 더 짧은 경로로 온적이 있는 지 판단했지만, 결국 여러번 해야돼서 최악의 경우(경로가 조금씩 주는경우) 최대의 시간복잡도와 크게 다르지 않습니다. 그래서 그때 그때 최소의 경로로 이동 하는 다익스트라를 사용하여 최소의 경우로 도달하면 다른 경로를 더이상 보지 않아도 되므로 굉장히 빠른시간내에 판단할 수 있습니다. 다만 2차원에서의 다익스트라를 해보지 않았다면, 어색할 수 있기 때문에, 다익스트라의 원리를 이해하고 원래 쓰던 코드에서 어느부분을 바꿔야하는지 아는것이 필요할것 같습니다.