• 출처 : 아기 상어

• 풀이 방법 : 최단 경로 (벨만포드)

• 순서

  1. 모든 노드까지 거리 구하기(relax 연산 반복)
  2. 거리가 최소인 노드로 이동
  3. 반복

• relax 연산 방법

  • 목표 노드까지의 거리 > 직전 노드까지의 거리 + 에지 크기 이면
  • 목표 노드까지의 거리 = 직전 노드까지의 거리 + 에지 크기

• 소감

  • python3로 제출 시 시간초과, pypy3로 제출 시 정답 ㅜ
  • 다 풀고 나서 BFS가 생각남..
  • 이후 더 공부해보니 다익스트라 알고리즘을 사용했으면 복잡도가 더 나아졌을 것 같다

코드

def relax(dist, i, j):

    if i-1 >= 0 and dist[i][j] > dist[i-1][j] + 1:
        dist[i][j] = dist[i-1][j] + 1

    if j-1 >= 0 and dist[i][j] > dist[i][j-1] + 1:
        dist[i][j] = dist[i][j-1] + 1
    
    if j+1 < len(dist) and dist[i][j] > dist[i][j+1] + 1:
        dist[i][j] = dist[i][j+1] + 1
    
    if i+1 < len(dist) and dist[i][j] > dist[i+1][j] + 1:
        dist[i][j] = dist[i+1][j] + 1


n = int(input(''))

result = 0
eat_count = 0

currw = 2
curri = -1
currj = -1

room = []
for i in range(n):
    
    temp = list(map(int, input('').split(' ')))
    room.append(temp)

    if 9 in temp:
        curri = i
        currj = temp.index(9)


while True:

    dist = [[float('inf') for j in range(n)] for i in range(n)]
    dist[curri][currj] = 0

    # set shortest path distance
    for y in range(n):
        for x in range(n):

            for i in range(n):
                for j in range(n):

                    if room[i][j] <= currw:
                        relax(dist, i, j)

    # get min
    mini = -1
    minj = -1
    minv = float('inf')
    for i in range(n):
        for j in range(n):
            if room[i][j] != 9 and room[i][j] != 0 and room[i][j] < currw and minv > dist[i][j]:
                minv = dist[i][j]
                mini = i
                minj = j

    if minv == float('inf'):
        break

    # move
    room[mini][minj] = 9
    room[curri][currj] = 0

    curri = mini
    currj = minj

    result += minv
    eat_count += 1    
    if eat_count == currw:
        currw += 1
        eat_count = 0

print(result)