[Programmers] 배달_Java

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

프로그래머스

문제

 

 

문제 해설

특정 거리로 서로 연결된 graph가 주어진다. graph의 1번 노드에서 다른 노드까지의 거리가 K 이하인 마을의 개수를 반환하면 된다.

 

 

 

문제 풀이

처음에 단순히 dfs로 풀려고 하였으나, 체계적이지 않은 코드 구성으로 인해 자꾸 틀렸고, 틀린 부분을 찾기 어려워서 다익스트라 알고리즘 대표 코드를 찾아보아서 적용했다.

* 다익스트라 알고리즘
DP 알고리즘 유형 중 하나이다. 큰 문제를 작은 문제로 나눌 수 있기 때문이다.
특정 노드에서 다른 노드까지의 최단거리는 min(기존의 다른 노드까지 거리, 새로운 다른 노드까지의 거리)를 반복하여 갱신할 수 있기 때문이다.

로직은 아래 블로그에서 자세히 설명되어 있다.

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

요약하자면,

(1) 기준노드 설정
(2) 기준노드와 연결된 노드들의 최소거리(비용) 갱신
(3) 방문 안한 노드들 중, 최소거리인 노드를 기준노드로 설정

위 로직을 모든 노드를 방문하여 최소거리를 갱신할 때까지 반복하는 것이다.

---

* 풀이

먼저, 다익스트라 알고리즘으로 본 문제를 풀기 위해서는
1. 방문노드체크 리스트 (checked)
2. 노드별 최단거리 리스트 (cost)
3. 노드1, 노드2, 거리 리스트
가 있으면 된다.

3.은 문제에서 int[][] road로 주어졌다.

 

(1) checked, cost 리스트를 초기화 및 선언해준다.
  - 2 리스트는 최대거리(K + 1)로 초기화 해준다.

(2) cost에서 0번 노드(기준점)의 비용을 0으로 바꿔준다.
  - 기준점에서 기준점의 비용은 0

(3) 모든 노드를 방문할 때까지 아래 로직을 반복한다.
  1. 다음에 방문할 노드(loc)와 현재 최단거리(valNow)를 -1, K + 2로 초기화해준다.
  2. checked의 size만큼 for문을 돈다.
     1. checked[i]를 방문한 적이 없고, checked[i]가 valNow보다 작다면 loc와 valNow를 i, cost[i]로 갱신해준다.
  - i가 -1이라면 더이상 방문할 노드가 없으므로 break한다.
  3. road를 for문으로 돈다
     1. road[0] 혹은 road[1]이 i이고 방문한 적이 없다면, 해당 노드의 cost를 갱신해준다.
         ex) road[0]의 cost를 min(road[1] cost, road[0] cost + road[2])
         - road[2]는 road[0] <-> road[1]로 가는 거리

 

* 풀이방법은 동일하게 생각해냈으나, 한번 정립된 알고리즘을 써야지 필요한 자원이나 로직 구현을 더욱 수월하게 할 수 있는 것을 확실히 느꼈다. 문제를 보고 적용해야 할 알고리즘을 최대한 빨리 떠올리고 적절하게 구현할 수 있어야 할 것 같다.

 

* 코드

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;

class Solution {

    public static int solution(int N, int[][] road, int K) {
        ArrayList<Boolean> checked = new ArrayList(Collections.nCopies(N, false));
        ArrayList<Integer> cost = new ArrayList(Collections.nCopies(N, K + 1));

        cost.set(0, 0);
        int loc;
        int valNow;

        while(checked.contains(false)){
            loc = -1;
            valNow = K + 2;

            for(int i = 0; i < checked.size(); i++){
                if(checked.get(i) == false && cost.get(i) < valNow){
                    loc = i;
                    valNow = cost.get(i);
                }
            }

            if(loc == -1){
                break;
            }
            
            checked.set(loc, true);
            
            for(int[] r:road){
                if(r[0] - 1 == loc && checked.get(r[1] - 1) == false){
                    cost.set(r[1] - 1, Math.min(cost.get(r[1] - 1), cost.get(r[0] - 1) + r[2]));
                }
                if(r[1] - 1 == loc && checked.get(r[0] - 1) == false){
                    cost.set(r[0] - 1, Math.min(cost.get(r[0] - 1), cost.get(r[1] - 1) + r[2]));
                }
            }
        }
        
        int answer = 0;
            
        for(int i:cost){
            if(i <= K){
                answer += 1;
            }
        }

        return answer;
        
    }
}