사용자 도구

사이트 도구


ps:problems:boj:4485

녹색 옷 입은 애가 젤다지?

ps
링크acmicpc.net/…
출처BOJ
문제 번호4485
문제명녹색 옷 입은 애가 젤다지?
레벨골드 4
분류

다익스트라

시간복잡도O(t*n^2logn)
인풋사이즈t<=?, n<=125
사용한 언어Python
제출기록42256KB, 188ms
최고기록120ms
해결날짜2022/09/19

풀이

  • 그리드에서 최단 경로를 찾는 문제.
  • 웨이트가 없는 경우에 그리드를 그래프로 모델링해서 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()

토론

댓글을 입력하세요:
W M A H Q
 
ps/problems/boj/4485.txt · 마지막으로 수정됨: 2022/09/19 16:39 저자 teferi