[프로그래머스] 배달 Java

programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

문제 요약

마을의 개수 N, 간선과 그 가중치의 배열 road, 최대 배달 가능 거리 K가 주어진다. 1번 마을에서 부터 배달을 출발하여 거리가 K가 넘지 않는 마을까지 배달이 가능하다. 배달이 가능한 마을의 개수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

 가중치가 할당된 그래프 문제이다. 처음에는 DFS 함수를 하나만들어서 재귀를 이용하며 마을을 여러 루트로 방문해보는 방법을 사용하였다. 문제는 정답처리되었지만 테스트 케이스의 마을과 간선의 개수가 최대치에 근접하면 실행시간이 비 정상적으로 길어졌다.

 

 이러한 문제를 해결하고자 다익스트라 알고리즘을 사용하여 문제를 다시 해결하였다. 거리 배열을 모두 최대값으로 초기화 한 후 출발점과 인접한 마을들만 거리를 다시 초기화 해주었다. 그 후 다익스트라 구현 함수내에서 반복문을 돌려서 출발점에서 가장 가까운 마을 순으로 그 마을의 인접한 마을들의 거리를 현재와 비교하여 다시 초기화해주었다. 함수가 종료된 후 Stream을 통해 거리 배열에서 K 이하의 값들의 개수를 반환해주었다.

 

 답안을 다시 제출 한 결과 정점과 간선의 수가 많지 않은 테스트 케이스들은 실행시간이 비슷하거나 오히려 미세하게 높은 경우도 있었지만, 정점과 간선이 매우 많은 케이스의 경우에는 엄청난 효율성 증가 효과를 얻었다. 앞으로 가중치가 할당된 그래프 문제를 다시 만난다면 뒤도 안보고 다익스트라로 풀어야겠다.

 

나의 코드

package programmers.graph;

import java.util.Arrays;

class 배달 {
    int[] d;
    boolean[] v;
    int[][] map;

    public int solution(int N, int[][] road, int K) {
        d = new int[N + 1];
        v = new boolean[N + 1];
        map = new int[N + 1][N + 1];

        // 간선 배열 채우기 (간선이 없다면 int 최대값)
        for (int i = 0; i <= N; ++i)
            Arrays.fill(map[i], Integer.MAX_VALUE);
        for (int[] i : road) {
            if (i[2] < map[i[0]][i[1]])
                map[i[0]][i[1]] = map[i[1]][i[0]] = i[2];
        }

        dijkstra(1);

        // 방문할 수 있었던 마을의 개수 반환
        return (int) Arrays.stream(d).boxed()
                .filter(i -> i <= K)
                .count() - 1;
    }

    /* 다익스트라 알고리즘 구현 함수 */
    private void dijkstra(int start) {
        d[start] = 0; //
        v[start] = true;
        for (int i = 2; i < d.length; ++i)
            d[i] = map[start][i];

        for (int i = 0; i < d.length - 2; ++i) {
            int minIdx = getMinIdx();
            v[minIdx] = true;
            for (int j = 2; j < d.length; ++j){
                if (map[minIdx][j] != Integer.MAX_VALUE && d[minIdx] + map[minIdx][j] < d[j])
                    d[j] = d[minIdx] + map[minIdx][j];
            }
        }
    }

    /* 시작점에서 방문할 수 있는 간선 중 최소값 찾기 */
    private int getMinIdx() {
        int minValue = Integer.MAX_VALUE;
        int minidx = 0;
        for (int i = 2; i < d.length; ++i) {
            if (!v[i] && d[i] < minValue) {
                minValue = d[i];
                minidx = i;
            }
        }
        return minidx;
    }
}