녹색 옷 입은 애가 젤다지?

• 그리드에서 최단 경로를 찾는 문제.
• 웨이트가 없는 경우에 그리드를 그래프로 모델링해서 BFS로 최단 경로를 찾는 문제는 너무 흔한 패턴이다. 이 문제는 그리드의 밸류들이 웨이트에 해당되므로, 같은 방식으로 웨이티드 그래프로 모델링해서 다익스트라 알고리즘으로 풀면 끝.
• 시간복잡도는 O(ElogV)이고 E=O(n^2), V=O(n^2)이므로 O(n^2logn)이 된다.

"""Solution code for "BOJ 4485. 녹색 옷 입은 애가 젤다지?".

- Problem link: https://www.acmicpc.net/problem/4485
- Solution link: http://www.teferi.net/ps/problems/boj/4485

Tags: [Dijkstra]
"""

import itertools
import sys
from teflib import graph as tgraph


def main():
    for prob_no in itertools.count(start=1):
        n = int(sys.stdin.readline())
        if n == 0:
            break
        grid = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)
               ]

        grid_arr = list(itertools.chain.from_iterable(grid))
        wgraph = [
            {v: grid_arr[v] for v in adj_u} for adj_u in tgraph.GridGraph(n, n)
        ]
        source, dest = 0, n * n - 1
        costs = tgraph.dijkstra(wgraph, source, dest=dest)
        cost_to_dest = grid_arr[0] + costs[dest]

        print('Problem {}: {}'.format(prob_no, cost_to_dest))


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.GridGraph, teflib.graph.dijkstra