[프로그래머스 12978] 배달 (Java)

[링크]https://programmers.co.kr/learn/courses/30/lessons/12978)

나의 코드

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

        // 경로 값의 무한값 설정 (c의 최대값 * N-1)
        final int INF = 20000 * (N-1);

        // 지나간 마을인지 확인하는 배열 생성
        boolean[] check = new boolean[N];   // 초기값 : false
        int[] value = new int[N];

        // 경로를 저장하는 N*N의 배열 생성
        int[][] table = new int[N][N];

        // table 초기화
        for (int i = 0; i < N; i++) {

            // value도 여기서 초기화
            value[i] = INF;

            for (int k = 0; k < N; k++) {
                table[i][k] = INF;
            }
            table[i][i] = 0;    // 자신에겐 0
        }

        // road의 입력받은 경로 값 저장
        for (int[] r : road) {
            // 양방향이므로 반대도 저장
            // 도시간의 도로는 여러개가 있을 수 있기 때문에
            // 값이 적은 하나의 도로만 남겨두기로 함

            if (table[r[0] - 1][r[1] - 1] > r[2]) {
                table[r[0] - 1][r[1] - 1] = r[2];
                table[r[1] - 1][r[0] - 1] = r[2];
            }

        }
        // 테이블 값 확인
        /*
        for (int[] y : table) {
            for (int x : y) {
                System.out.print(x + " ");
            }
            System.out.println();
        }
        */

        // 문제에서는 무조건 1번에서 출발하기 때문에, 1번부터 확인
        // 마을은 1~N번마을까지 있고, 실제로는 0~N-1로 접근하니까 헷갈리지 않도록 주의
        int start = 0;
        value[start] = 0;   // 출발점이기 때문에 0으로 변경

        do {
            check[start] = true;    // 방문 기록 체크

            for (int i = 0; i < N; i++) {
                // 이전의 최소값 보다 지금까지 값 + 현재 도로 값 이 작으면 갱신

                if (value[start] + table[start][i] < value[i]) {
                    // 갱신
                    value[i] = value[start] + table[start][i];
                }
            }

            // 다음 출발 값 확인
            start = -1; // 출발값 초기화
            int min = INF;

            // 아직 방문하지 않았고, 경로값이 가장 적은 노드를 탐색
            for (int i = 0; i < N; i++) {
                if ((check[i] == false) && (value[i] < min)) {
                    start = i;
                    min = value[i];
                }
            }

        } while(start != -1);

        // 각 노드별 계산된 최소값 확인
        /*
        for (int a : value) {
            System.out.print(a + " ");
        }

        System.out.println();
        */

        for (int val : value) {
            if (val <= K) {
                answer++;
            }
        }

        return answer;
    }
}

경로 탐색에 대한 알고리즘은 필요할 것 같아서 개념을 확인하고 풀어보았다.
다익스트라 알고리즘의 기본 개념은 노드를 탐색하면서 현재까지의 경로가 더 적을 경우 그 경로를 우선순위로 한다는 것이다. 정확한 개념 풀이는 다른 블로그를 참조하는 게 좋겠다.

모범 답안

class Solution {
    public int solution(int N, int[][] road, int K) {

        int matrix[][] = new int[N][N];
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                matrix[i][j] = 0;

        for(int i=0;i<road.length;i++) {
            if(matrix[road[i][0]-1][road[i][1]-1] == 0 || 
              matrix[road[i][0]-1][road[i][1]-1] > road[i][2])
                matrix[road[i][0]-1][road[i][1]-1] = 
                    matrix[road[i][1]-1][road[i][0]-1] = road[i][2];
        }

        boolean visits[] = new boolean[N];
        int costs[] = new int[N];
        for(int i=0;i<N;i++) {
            visits[i] = false;
            costs[i] = Integer.MAX_VALUE;
        }

        costs[0] = 0;
        int target = 0;
        while(true) {
            visits[target] = true;
            for(int i=0;i<N;i++)
                if(matrix[target][i] > 0) {
                    if( costs[i] > costs[target] + matrix[target][i])
                        costs[i] = costs[target] + matrix[target][i];
                }

            target = -1;
            for(int i=0;i<N;i++)
                if(!visits[i]) {
                    if(target == -1 || costs[target] > costs[i])
                        target = i;
                }

            if(target == -1)
                break;
        }

        int answer = 0;
        for(int i=0;i<N;i++) {
            if(costs[i] <= K)
                answer++;
        }

        return answer;
    }
}

대부분 같은 형식이다. 다만 어느 블로그 글에서 초기 값을 Integer.MAX_VALUE로 했을 때 문제가 생긴다는 글이 있어 나의 경우는 MAX 값을 별도의 수로 지정했다.
그 부분을 제외하고는 아래의 코드가 훨씬 간결하다고 생각한다.