[프로그래머스] 배달 (JAVA/자바)

문제 링크

풀이

전형적인 다익스트라 문제이다. 1번 마을로부터 다른 마을까지 갈 수 있는 최소 거리를 구한 뒤에, k보다 같거나 작은 경우만 카운트 해주면 된다.

<다익스트라 알고리즘 구현>

1. A를 시작점으로 했을 때의 다른 도시까지의 거리에 대한 정보를 dist[]로 선언하여 초기화한다. 가는 길이 존재한다면 해당 weight를, 경로가 존재하지 않으면 무한대(500001) 값으로 초기화한다.
2. 다른 도시를 방문했는지 여부를 체크하기 위해 visited[]를 선언한다.
3. 시작점을 제외하고 dist[]의 값이 가장 작은 도시의 index를 가져온다. (EXTRACT-MIN)
4. 해당 index를 visited 처리 한 뒤, 그 index의 도시를 거쳐가는 경로가 원래 dist[]에 들어있는 값보다 작으면 값을 변경한다.
5. 3~4번을 n-1번 반복한다.

• Extract-Min 할 때 Priority Queue를 사용하고, 간선 정보를 인접리스트로 구현하면 좀 더 효율적인 코드를 작성할 수 있다.
• 무한대 값을 500001으로 설정한 이유는 최대 노드 개수(=최대 거칠 수 있는 간선의 개수) * 간선의 최대 weight
  • N의 개수 (50) * 간선의 최대 weight (10000) + 1

코드

class Solution {
    static final int INF = 500001;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        int[][] map = new int[N + 1][N + 1];
        
        // 무한대로 초기화
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if(i==j) continue;
                map[i][j] = INF;
            }
        }

        // 간선 정보 저장 (이중 배열)
        for (int i = 0; i < road.length; i++) {
            int a = road[i][0];
            int b = road[i][1];
            int w = road[i][2];

            if (map[a][b] > w) {
                map[a][b] = w;
                map[b][a] = w;
            }
        }

        int[] dist = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            dist[i] = (dist[i]==0) ? INF : map[1][i];
        }

        boolean[] visited = new boolean[N + 1];
        visited[1] = true;

        for (int i = 1; i <= N - 1; i++) { // n-1번 반복

            // extract-min
            // dist 중에 방문하지 않았고 가장 작은 값을 가지는 인덱스를 찾는다.
            int min_idx = 1;
            int min_value = INF;
            for (int j = 2; j <= N; j++) {
                if (!visited[j] && dist[j] < min_value) {
                    min_value = dist[j];
                    min_idx = j;
                }
            }

            visited[min_idx] = true;

            // 거쳐가는게 더 빠른지 확인
            for (int j = 2; j <= N; j++) {
                if (dist[j] > dist[min_idx] + map[min_idx][j]) {
                    dist[j] = dist[min_idx] + map[min_idx][j];
                }
            }
        }

        // 결과 카운트
        for (int i = 1; i <= N; i++) {
            System.out.println(dist[i]);
            if(dist[i]<=K) answer ++;
        }


        return answer;
    }
}

정리

난이도 : LEVEL 2

🤦‍♀️ 메모

• 다익스트라 알고리즘 맨날 까먹는다... 진짜 이제는 좀 기억을 잘 해보자!
• Extract-Min 할 때 Priority Queue랑, 인접리스트로 구현하는거 해보기!

참고 사이트

딱히 없음