배달

링크텍스트

문제 설명

1. road[시작, 끝, 거리]로 되어있다. 마을 1에서 다른 마을까지 가는 최단 거리를 구한다.
2. 그 최단 거리가 K보다 작은 마을을 세어준다.

시행착오 및 문제 풀이

우선!!!!!! 다익스트라 알고리즘 풀이인줄 몰랐어요
최단 거리... 최단 거리 어디서 많이 들어봤는데? 하고 구글링 하다가
아 다익스트라구나! 했죠 하지만 풀이 방법을 모르는걸..~

그래서 꽤나 많은 시행착오를 겪은 문제.. 풀이 먼저~

정답 풀이

1. 거리의 최솟값을 갱신하기 위해 조건상 가장 큰 값인 500000으로 모든 거리를 초기화해준다.

2. road의 값을 넣어준다.
   2-2. 이때, 2번째 예의 경우 [3,5,2],[3,5,3]와 같이 같은 마을에서 같은 마을로 가는 도로이지만 거리가 다른 도로가 있을 수 있다. 그러므로 이미 더 작은 값이 들어가 있다면 갱신하지 않고 넘어가준다.

3. 3중 for문을 돌려준다.
   3-1. 경유하는 마을을 중심으로 시작 마을과 마지막 마을의 거리를 구한다. 이때, 더 작은 값이 있다면 최솟값으로 갱신해준다.

4. 마을의 모든 거리를 구한 후 k보다 작은 거리로 갈 수 있는 마을을 세어준다.
   4-1. 이때, 1번 마을에서 시작하는 거리만 구하면 되므로 map[0][i]로 구해준다.

정답 코드

//최단거리 -> 다익스트라 알고즘
import java.util.*;
class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        int[][] map = new int[N][N];
        //거리를 최솟값으로 갱신하기 위해 가장 큰 값 넣어주기
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                //나 자신은 거리를 0으로 처리
                if(i==j) {
                    map[i][j] = 0;
                }
                else {
                    map[i][j] = 500000;
                    map[j][i] = 500000;
                }
            }
        }
        
        //road 값 넣어주기
        for(int[] r:road) {
            //이미 더 작은 값이 들어가있다면 갱신하지 말고 넘어가기
            if(map[r[0]-1][r[1]-1] < r[2]) {
                continue;
            }
            map[r[0]-1][r[1]-1] = r[2];
            map[r[1]-1][r[0]-1] = r[2];
        }
        
        //다익스트라 알고리즘
        
        //경유
        for(int i=0; i<map.length; i++) {
            //시작
            for(int j=0; j<map.length; j++) {
                //마지막
                for(int k=0; k<map.length; k++) {
                    //경유하는 것이 더 작다면 그것으로 갱신
                    if(map[j][k] > map[j][i] + map[i][k]) {
                        map[j][k] = map[j][i] + map[i][k];
                    }
                }
            }
        }
        
        //k보다 작은 것
        for(int i=0; i<map.length; i++) {
            if(map[0][i] <= K) {
                answer++;
            }
        }
        
        return answer;
    }
}

정답!! 이지만 사실 풀이를 참고하면서 풀었기 때문에 의문점이 생긴 부분이 있다.
바로

//경유
        for(int i=0; i<map.length; i++) {
            //시작
            for(int j=0; j<map.length; j++) {
                //마지막
                for(int k=0; k<map.length; k++) {
                    //경유하는 것이 더 작다면 그것으로 갱신
                    if(map[j][k] > map[j][i] + map[i][k]) {
                        map[j][k] = map[j][i] + map[i][k];
                    }
                }
            }
        }

이 부분이다..
왜 경유하는 부분이 제일 바깥쪽 for문이지???
단순하게 생각했다면 시작 -> 경유 -> 마지막 이런식으로 for문을 돌렸을 것 같은데.. 내가 다익스트라나 플로이드 워셜 알고리즘을 잘 몰라서 이런 의문이 드는건가.. 싶어서 열심히 구글링했다.

이해하는데만 2시간 걸렸다..! 생각보다 간단한 부분이였는데 바보같아ㅜㅜ

오답 풀이

[경유 -> 시작 -> 마지막 순으로 for문을 돌려야 하는 이유]

만약, 시작 -> 경유 -> 마지막 순으로 for문을 돌리면 경유하는 부분의 최단거리가 제대로 갱신되지 않는다.
우선 프로그래머스에서 제공된 예를 좀 바꿔보자면

이 그림에서 2마을을 6마을이라고 임의로 바꿔봤다.
그리고 2->3을 8로 임의로 바꿨다.

1->3의 거리를 구한다고 했을 때, 1->6->5->3 = 4이고, 1->6->3 = 9이다.
그럼 1->3의 가장 작은 거리는 4이다.
그렇지만 시작을 기준으로 경유 -> 마지막 순으로 for문을 돌리게 되면
시작:1, 경유:5, 마지막:3이다.
아직 시작:1, 경유:6, 마지막:5 인 거리를 갱신하지 않았기 때문에 최댓값이 설정되어 있다.
그러므로 1->6->5->3은 500001이 된다. 이것은 최솟값을 보장하지 않는다.
그러므로 경유 -> 시작 -> 마지막 순으로 for문 돌려야 한다.

이게 헷갈렸던 이유가 프로그래머스에서 제시한 예에서는 돌아갔고 시작 for문을 기준으로 해도 틀리지 않았기 때문에 엄청 오래 걸렸다.
그래서 내가 임의로 숫자도 바꿔보고... 해서 이해했다.. 힘들었다.

새롭게 알게 된 점

다익스트라 알고리즘: 한 정점에서 모든 최단 경로
플로이드 워셜 알고리즘: 모든 정점에서 모든 최단 경로

만약 이 문제에서 1번 마을에서 시작하는 게 아니라 모든 마을에서 최단 거리를 구해라 했더라면 마지막 for문을 이중 for문으로 구성하면 될듯하다. (이건 내피셜이다. 틀릴 수도 있다.)

---

다익스트라 알고리즘 이름도 어렵고 발음도 어렵고 원리도 어렵고 코드는... 그렇게 어렵진 않았지만 무진장 헷갈렸다
다익스트라 너도 짜증나는 코테 리스트에 추가