[플로이드]실수했던 것중 의미있었던 코드들.

플로이드에 대해서는 다익스트라글에서 확인해.

오늘 플로이드 문제를 다시한번 풀어보다가 괜찮겠지?라고 생각하고 넘어갔다가 오답에 결정적인 기여를 한 코드 2개를 살펴볼거야.

먼저 첫번째

내가작성한 코드

for (int i = 1; i <= node; i++) {
        for (int j = 1; j <= node; j++) {
            for (int k = 1; k <= node; k++) {
                if (distance[i][k]!=INF && distance[k][j]!=INF) {
                    distance[i][j] =min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }

정답인 코드

for (int k = 1; k <= node; k++) {
        for (int j = 1; j <= node; j++) {
            for (int i = 1; i <= node; i++) {
                if (distance[i][k]!=INF && distance[k][j]!=INF) {
                    distance[i][j] =min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }

자!! 지금 보면 코드의 내용은 같은데 k와 i의 위치만 달라져있어. 내가 습관적으로 작성한 코드는, ijk순서로 생각나는대로 작성한 코드인데 오답처리가 되었는데 왜 잘못되었을까??

첫번째 코드의 문제점으론 3단계로밖에 길이를 결정할 수 없어. 이게 가장 큰 문제야 예를들어 (2,1)로 향하는 최소값을 알고 싶다고 했을 때 2->5->4->1의 길밖에 없다고 치면 내가 작성한 코드는 2,5,4노드를 찾다가 존재하지 않으므로 if를 건너 뛰는 것을 확인 할 수 있었어. 무심결에 되겠지..? 라고 생각하고 넘어간 것이 잘못됐던거 같아.

플로이드 알고리즘은 먼저 k=1 부터 시작하여  k=node때까지 distance를 구하게 되면 모든 구간의 최소 distance를 구할 수 있다라는 알고리즘이므로 중간값에 해당하는 k를 반복문 제일 바깥으로 넘겨야 해. k값이 올라갈 수록 최소값이 갱신되는것을 확인할 수 있어. 웃긴건 i와 j는 먼저오나 나중에오나 순서에 상관이 없다는 점? 개념적으로는 매우 간단한 알고리즘인데 하나하나 순서를 따지니까 머리가 복잡하네. 원래 이런 알고리즘이라는것만 일단 기억해두자.! 즉 k가 올라갈 수록 최소비용이 업데이트되는 식이야.

for (int i = 1; i <= node; i++) {
        for (int j = 1; j <= node; j++) {
            if (i == j||distance[i][j]==INF) cout << 0<<" ";
            else cout << distance[i][j] << " ";
        }
        cout << endl;
    }

둘쨰로 결과값을 출력할 때에 발생한 실수이다. i와 j가 같으면 동일한 노드이므로 0을 출력하면 되었는데 경로가 없는경우를 생각하지 않고 distance[i][j]=inf를 쓰지않아 오답처리되었다. 조건을 잘읽어야하는데 항상 빼놓는 것 같은데 주의해야되겠다.