방금 풀어서 맞았는데 아마 긴 글이 될 것 같군요....

우선 질문자님 접근 방식은 시간초과가 뜰 것입니다.

왜냐하면 각 점에서 다익스트라를 돌리시는데 다익스트라가 O(Vlog E + E)인데 E가 최대 V^2까지 들어오니

O(V^2)이라고 생각할 수 있고 각 점마다 돌리시니 최종적으로는 O(V^3)이 되어 플로이드 와샬과 동일해집니다.

문제를 잘 읽으시면 규칙을 확인할 수 있습니다.

다음을 수학적으로 증명해보시기 바랍니다.

임의의 노드 a,b 사이의 길이 k인 path S은 다음과 같이 나타낼 수 있다.(S_1=a,S_k=b)

S_1 -> S_2 -> S_3 -> ... -> S_k

이 path가 존재한다면 다음 path가 존재한다.

(S_1+1)%N -> (S_2+1)%N -> .... ->(S_k+1)%N

즉 a,b 사이에 path가 있으면 (a+1)%N,(b+1)%N 사이에 path가 존재한다.

위 사실로부터 다익스트라를 한번  돌리면 답을 얻을 수 있습니다.

그런데....이 문제 메모리가 굉장히 타이트합니다.

priority queue로 구현하면 동일 노드가 큐 안에 여러번 존재할 수 있고 공간복잡도적으로 좋지 않습니다.

노드의 수가 적으니 시간복잡도를 다소 포기하고 공간복잡도를 좋게 개선하시면 정답을 맞추실 수 있을겁니다.

이건 그렇게 어렵지 않으니 한번 고민해보시기 바랍니다.

만약 하시다 막히시면 이 글에 답글 달아주세요

아....그런데 priority queue를 써서 맞추신 분이 계시네요...최적화를 잘하면 priority queue로도 구현 가능한 것 같습니다

답변 감사합니다 !

친절하게 설명해주셨는데 제가 모르는 게 많아 몇 차례 다시 읽어도 이해되지 않는 부분이 많네요 ㅠ

먼저 E가 최대 V^2 만큼 들어올 수 있다는 부분이 이해가 되지 않습니다.

제가 알고 있기로는 E는 한 노드에 연결된 간선의 개수로 알고 있는데 이 문제에서 한 노드에 연결되는 간선의 개수는 2*(V-1)로 모두 동일하지 않나요?

a,b 사이에 path가 있으면 (a+1)%N,(b+1)%N 사이에 path가 존재한다. 는 명제가 이해 되지 않습니다. ㅠ

임의의 노드 a,b에 대해서 a+1, b+1이 무엇을 의미하는지 (a+1)%N은 또 무엇을 의미하는지 모르겠어요.

시간복잡도를 포기하고 공간복잡도를 개선할 방법을 고민해보라고 하셨는데

제 딴에는 여러 차례 고민해봤지만 도저히 답을 구할 수 없었습니다. ㅠㅠ

여러모로 도움을 주셨는데 제가 부족해서 많이 못 받아가네요.

이 문제 조금 어려운 편이여서 처음엔 좀 난감할 수 있습니다.

하지만 어려운 만큼 많은 것을 배우실 수 있을 거라 생각합니다.

E가 최대 V^2까지 들어올 수 있다는 것에는 사실 전재조건이 있습니다.

두 노드 사이의 엣지의 수가 O(1)으로 고정되어있어야한다는 것입니다.

예를 들어 무방향그래프에서 모든 노드들이 연결되고 (임의의) 두 노드 사이의 엣지는 하나만 있을때 엣지의 수는 조합으로 구할 수 있고

_VC₂=V(V-1)/2 이므로 O(V^2)입니다.

이 문제의 경우 E가 V개 들어오는 것 처럼 보이지만 정확히는 A가 들어오는 것입니다.

A가 모두 양수이면 모든 노드들이 연결되어 있는 것이고 그렇다면 위에 보였듯이 O(V^2)입니다.

(유향그래프도 E도 O(V^2)입니다. 비슷한 방법으로 증명가능합니다.)

그리고 이미 말씀하신 내용에서 조금만 더 내용을 진전시키면 같은 결과를 얻을 수 있습니다.

한 노드에 연결되는 엣지의 갯수는 2(V-1)이라고 하셨습니다.

이게 한 노드니까 그래프 전체의 엣지의 갯수는 2V(V-1)인데 이렇게 세면 엣지를 두번 세는 셈이므로

(a->b 엣지를 a노드 셀 때 b노드 셀 때 총 2번 세므로)

전체 엣지의 갯수는 V(V-1)입니다.

물론 A에 0이 있다면 V(V-1)보다는 적겠지요.

a,b가 숫자입니다. 예를 들어 n(정점의 수)가 9, a가 3, b가 8이라 하겠습니다.

3에서 8로 갈 수 있는 path가 존재하고 그 path가 다음과 같다고 한다면

3->5->0->8

4에서 0으로 가는 cost가 동일한 path가 존재하는데

4->6->1->0

다음과 같이 path의 노드 각각을 (원래 노드 + 1)%n로 바꾼 것입니다.

그리고 "임의의"라는 표헌을 쓴 것은 이것이 특정 노드들에 대해서 성립하는 것이 아니라 모든 노드들에 대해서 성립하는 말이기 때문입니다.

다익스트라에서 priority queue를 왜 사용하는지 생각해보면, 지금까지 visit한 노드들로부터 갈 수 있는 노드들 중에 최솟값을 찾기 위함입니다.

만약 priority queue 대신 brute search를 하게 되면 시간복잡도는 O(log E) = O(log V)에서 O(V)로 증가하지만 공간복잡도가 O(E)=O(V^2)에서 O(V)로 줄어듭니다.

막히시거나 궁금하신 내용있으시면 다시 답글달아주세요.

친절한 설명 정말 감사합니다 !!

전혀 감을 못 잡고 있었는데 계속 보다보니 조금씩 길이 열리는 것 같아요.

말씀하신대로 a ->b 로 가는 경로가 존재할 때 a+1 -> b+1 로 가는 경로가 존재한다는 점에 착안해서 새로 코드를 짰습니다.

각 노드에서 다른 노드로의 초기 거리를 저장하는 이중 리스트 conn을 1차원 리스트로 만들었더니 메모리 초과 문제를 해결할 수 있었습니다.

다만 python3으로 제출했을 때는 시간 초과 판정을 받더라구요 ㅠㅠ

pypy3으로 제출했을 때는 오래 걸리지만 정답 판정을 받긴 했습니다.

python3에서도 통과할 수 있도록 한 번 더 도전해보고 있는데

dijkstra를 구현하는 부분에서 시간을 줄이지 못하고 있습니다.

우선순위 큐를 사용하는 방법 외에 더 빠른 방법이 있을까요?

아니면 지금의 제 코드에 불필요한 로직이 들어가 있는 걸까요?

넵 우선 다익스트라의 구현이 잘못되었습니다.

다익스트라는 원리를 잘 생각해야합니다.

다익스트라는 이미 방문한 노드들로부터 갈 수 있는 노드들 중에 최단거리인 노드부터 방문하여 최단거리를 확정하는 알고리즘입니다.

prority queue에 들어가는 원소들은 해당 노드까지의 최단 거리가 아니라 가능성이 있는 노드들입니다.

위에 쓰신 코드를 보면 이전에 idx 노드가 priority queue에 있더라도 dis+conn[i]가 더 작다면 갱신합니다.

그렇다면 priority queue에 같은 노드가 2개 이상 있는 경우 두번째부터는 더 이상 볼 필요가 없습니다.

왜냐하면 그 이전에 더 빠른 경로로 해당 노드를 방문했을테고 그때 연결된 다른 노드들도 priority queue에 들어갔을 테니까요

그래서 minDis값의 갱신을 priority queue에서 pop했을때하면 되고 이전에 방문을 했다면 스킵하면 됩니다.

아래 수정된 코드 첨부해드립니다.(그대로 내면 메모리초과 뜰 것입니다. 아래를 읽어주세요)

그런데 그것과 별개로 이 문제의 메모리 제한이 굉장히 타이트합니다.

개조가 다소 필요합니다.

윗글에서 언급했듯 brute search를 하셔도 되고 아니면

주석처리되어있는 부분과 같이 짜셔도 됩니다.(주석처리 안된 pq부분을 지우고 주석처리된 곳을 주석해제시키시면 됩니다.)

priority queue에 넣기 전에 이 노드가 가능성이 있는지 없는지를 한번 더 확인하는 방법입니다.

질문자님 코드와 유사해보이지만 다른 점이 있습니다.

그것이 무엇일지 한번 고민해보시면 좋을 것 같습니다.

주석처리되어있는 부분과 주석처리되어있지 않은 부분의

시간복잡도, 공간복잡도 모두 같습니다.

다만 공간복잡도의 경우 주석처리되어있는 부분의 계수가 조금 더 낮습니다.

그 차이로 주석처리되어있는 코드로 제출하신다면 맞을 수 있습니다.

혹시 코딩테스트 준비하시나요? 실례가 안된다면 알고리즘 공부하시는 이유를 여쭤봐도 될까요?

막히신 부분이 있다면 또 답글 달아주세요

답이 늦어서 죄송합니다. ㅠㅠ

답변 달아주신 날 코드를 확인했는데 머리에 과부하가 걸렸는지 당일에는 도저히 이해하지 못하고 넘어갔어요.

사실 지금도 애매한 점이 많아 계속 다시 보고 있습니다.

먼저 하신 질문부터 답을 할게요. 코딩 테스트를 준비하고 있어요.

고난도 문제까지 다루지 않더라도 대부분의 코딩 테스트는 무난하게 통과할 수 있다고 들었지만 컴퓨터가 동작하는 방식을 이해하는데 도움이 된다고 생각해서

더 어려운 난이도의 문제도 접해보고 있습니다. 그런데 조금만 복잡해져도 금방 머리가 안 돌아가네요. ㅠㅠ

코딩에 처음 재미를 붙이게 된 것도 알고리즘 문제를 풀면서였고

초기에는 주변 사람들보다 성장하는 속도가 빨라서 그 재미로 더 열심히 했던 것 같네요.

이제는 한계에 다다랐는지 자주 벽을 느낍니다. 속도만 쫓다가 기본을 많이 놓친 것 같네요. ㅠㅠ

아하 그렇군요

애매하다고 생각하신 부분을 알려주시면 조금 더 자세히 설명해드리겠습니다.

코딩 테스트를 준비하시고 계시군요.

같이 문제 푸실레요?

저는 코딩테스트는 아니지만 알고리즘 조금씩 공부하고 있습니다.

관심 있으시면 제 메일(buzri1905@naver.com)으로 연락주세요.

많이 알려주셨는데 지금은 일을 늘릴 만한 여유가 없네요 ㅠㅠ

제안은 감사합니다. 좋은 하루 되세요 !