gyjinro   3년 전

문제에서 t가 50에 n의 최대가 100(실상 시작과 끝을 합치면 102)가 될 수 있어서..

n 이 약 5000이니 O(n^3) 알고리즘으로는 풀 수 없을 거라고 생각했습니다. 

나름대로 BFS를 만들어서 풀었는데 틀렸다고 나오길래 카테고리 확인하고 플로이드로 풀어서 맞추기는 했는데요.

가뜩이나 느린 파이썬으로 각 정점 당 가중치 계산까지 하면서 간선들을 확보해야 하는 상황에서

O(n^3)으로 1초 내에 풀이가 가능하다는 점이 이해가 잘 되지 않습니다.

다익스트라를 써야 하는게 아닌가 하고 한참을 고민해봤습니다.

이 문제의 n과 시간복잡도를 어떻게 파악 해야 할까요?

댓글을 작성하려면 로그인해야 합니다.