kons   8년 전

플로이드 와샬 알고리즘을 기반으로 간단하게 시도하였습니다.

입력이 N의 최대가 1000이라, 1000*1000 인 배열에서 삼중for문을 돌리는데

시간제한이 1초라 걱정은 했으나, 플로이드 와샬 알고리즘말고는 떠오르는 방법이 없네요.


질문 1.  시간 제한이 1초일때, 입력범위가 1000*1000일 경우,  플로이드 와샬 알고리즘(삼중for문)을 사용하면 안되는 것인가요?

질문 2. 다른 알고리즘을 사용해야한다면, 혹시 강력한 힌트 주실 수 있는 분 계신가요? 

kcm1700   8년 전

N=1000이라도 경우에 따라 N^3도 괜찮을 수 있습니다.

이 문제는 다른 알고리즘을 쓰시는 게 바람직해요. 어떤 최단 경로의 쌍이 필요한지 전부 나열해보세요. 모든 최단 경로의 쌍이 필요하지 않아요.

yukariko   8년 전

저도 다익스트라로 해결하긴 했지만 플로이드를 돌릴때 d[i][k] 가 inf인경우를 커트하는것으로 시간초과를면할 수 있습니다

kcm1700   8년 전

시간복잡도 분석을 해보세요.

graph가 있으면 각 edge의 방향을 뒤집은 graph에서도 생각해보세요.


kons   8년 전

그래프에 대한 문제를 처음 풀어봐서 참 많이 고민했는데, 명쾌한 조언들 감사합니다.

kcm1700님 조언대로 다익스트라로도 해결하였고, yukariko님 조언대로 플로이드로 시간초과를 면하였습니다.

감사합니다! 

kimdr123   8년 전

@Kons @yukariko


저도 다익스트라로 해결하긴 했지만 플로이드를 돌릴때 d[i][k] 가 inf인경우를 커트하는것으로 시간초과를면할 수 있습니다 이말이 무슨말인지


설명좀 부탁드려도 될까요?


이렇게 접근을 하고있는데요 어디를 커트해야할지 감이 안오네요.


yukariko   8년 전

map[i][k]가 INF라면 어차피 갱신이 이루어지지 않기때문에 건너뛰어도 괜찮습니다.

kimdr123   8년 전

@yukariko


건너뛴다고 하셔서 저는 map[i][k]=continue;로 접근했었는데 아예 루트를 빠져나와야 하는거였네요.


답변 감사합니다.

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