배달

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

Level 2

 

경로의 최소 비용을 구하기 위한 대표적인 다익스트라 알고리즘 문제

 

1번 마을에서 출발하여 2~N번 마을까지 각 마을마다 배달 가능한 최소 비용을 구한 뒤 

문제에서 제시한 K를 초과하지 않는 마을들의 갯수를 반환해야한다.

 

필자의 경우 다음과 같은 방식으로 다익스트라 알고리즘을 활용해 솔루션 구현했다. 

1. 1번 마을에서 2~N번 마을까지 방문하지 않은 마을 중 다익스트라 최소 비용이 가장 적은 마을을 찾는다.

2. 다익스트라 최소 비용 마을에서 인접한 다른 모든 마을까지의 거리를 다익스트라 비용과 비교한다.

3. 업데이트가 필요한 경우 다익스트라 최소 비용을 최신화 후 방문 처리한뒤 1번으로 돌아간다.

4. 더 이상 방문할 곳이 없다면 종료.

 

문제에서 제공한 예시를 통해 확인해보면 다음과 같다. 

 

 

최초 자기 자신에 대한 방문에 대한 비용은 0이니 처음 다익스트라 진행 시 1번 마을에서 시작한다.

이후 인접한 두 마을인 2, 4번 마을의 경로 까지 비용 + 자신의 다익스트라 비용 과  2, 4번 마을의 현재 다익스트라 최소 비용을 비교해 최신화 완료 후에 방문 처리한다. 

 

 

2번 째 수행 시 다익스트라 최소 비용 중 가장 작고 방문하지 않은 2번 마을에서 시작한다. 

2번 마을과 인접한 1, 3, 5 마을까지의 경로와 다익스트라 비교를 진행한다.

완료 후에 2번 마을을 방문처리한다.

 

 

3번 째 수행 시 다음 마을인 4번의 이웃 마을을 확인한다. 

하지만 이번엔 4번 마을까지의 비용 2 + 인접 마을 경로 비용과 인접 마을들의 현재 다익스트라 최소 비용 비교 시 최신화 할 부분이 없다. 따라서 그냥 방문 처리만하고 다음 마을로 넘어간다.

 

 

4번 째 수행 시 5번 마을의 이웃 마을을 확인한다.

마찬가지로 최신화할 내용이 없으므로 방문처리 후 다음 마을로 이동한다. 

 

 

5번 째 수행 시 3번 마을의 이웃 마을을 확인한다.

최신화할 내용이 없으므로 방문처리 이후 다음마을로 넘어가야 하지만,

더 이상 방문할 마을이 없으므로 다익스트라 로직을 종료한다. 

 

import java.util.*;

class Solution7 {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[][] costArr = new int[N+1][N+1]; //마을 간 비용 확인 용 배열
        int[] DST = new int[N+1]; //다익스트라 최소 비용 배열
        boolean[] visit = new boolean[N+1]; //방문처리 배열
        HashMap<Integer, ArrayList<Integer>> townMap = new HashMap<Integer, ArrayList<Integer>>(); //인접 마을 확인 용 리스트 맵
        init(costArr, townMap, DST, N, road); //사용 변수 데이터 입력 및 초기화

        while(!visitedAll(visit)) { //전체 방문 확인
            int minCost = Integer.MAX_VALUE; //다익스트라 최소 비용 중 최소값
            int minVillage = 0; //최소값인 마을

            for(int village = 1; village < DST.length; village++) {
                if(DST[village] < minCost && !visit[village]) { //방문처리되지 않은 마을 중 최소 비용인 마을 찾기
                    minVillage = village;
                    minCost = DST[minVillage];
                }
            }
            visit[minVillage] = true; //방문처리
            ArrayList<Integer> neighbors = townMap.get(minVillage); //인접 마을 가져오기
            for(int neighbor : neighbors) {
                DST[neighbor] = Math.min(DST[neighbor], DST[minVillage] + costArr[minVillage][neighbor]); //인접마을 간 비용 최신화
            }
        }
        //다익스트라 종료
        
        for(int village = 1; village < DST.length; village++) {
            answer = DST[village] > K ? answer : answer+1; //정답 반환을 위한 값 확인
        }

        return answer;
    }

    public boolean visitedAll(boolean[] visit) {
        for(int idx = 1; idx < visit.length; idx++)
            if(!visit[idx]) return false;
        return true;
    }

    public void init(int[][] costArr, HashMap<Integer, ArrayList<Integer>> townMap, int[] DST, int N, int[][] road) {
        for(int[] roadInfo : road) {
            int village1 = roadInfo[0];
            int village2 = roadInfo[1];
            int cost = roadInfo[2];

            if(costArr[village1][village2] > 0 && costArr[village1][village2] < cost)
                continue; //비용만 다른 같은 경로 예외처리

            costArr[village1][village2] = cost;
            costArr[village2][village1] = cost;

            customMapPut(village1, village2, townMap);
            customMapPut(village2, village1, townMap);
        }

        Arrays.fill(DST, Integer.MAX_VALUE); //다익스트라 무한대 값 입력
        DST[1] = 0; //자기 자신은 방문 시 0 처리
    }

    public void customMapPut(int key, int val, HashMap<Integer, ArrayList<Integer>> map) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list = map.containsKey(key) ? map.get(key) : list;
        list.add(val);
        map.put(key, list);
    }
}