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

문제

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

코딩테스트 연습 - 배달

 

접근법

이런 그래프 문제는 보통 인접 배열보단 인접 그래프로 푸는게 좋아서 인접 그래프를 사용했다.

result 배열에는 각 마을까지 가는데 걸리는 시간들을 담겨있다.

dfs를 통해서 풀었고 1번 마을은 무조건 배달이 가능하기 때문에 answer는 1로 초기화한 상태로 풀었다.

 

코드

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private ArrayList<ArrayList<int[]>> graph = new ArrayList<>();
    private int[] result;
    private int K, answer=1;
    public int solution(int N, int[][] road, int K) {
        this.K = K;
        result = new int[N+1];
        Arrays.fill(result, Integer.MAX_VALUE);

        graphInit(N, road);
        dfs(1, 0);
        return answer;
    }

    private void dfs(int n, int weight){
        //현재까지의 시간을 넣고
        result[n] = weight;

        for(int[] node : graph.get(n)){
            //현재까지의 시간에 연결된 다음 마을을 가는 시간을 더해서 sum에 저장    
            int sum = node[1] + weight;
            //sum이 만약 K를 넘어가거나 node[0]번 마을의 지금까지의 최솟값보다 크다면 continue
            if(K < sum || result[node[0]] < sum)
                continue;
            //아직 방문하지 않았다면 배달이 가능하므로 answer++    
            if(result[node[0]] == Integer.MAX_VALUE)
                answer++;
            dfs(node[0], node[1] + weight);
        }

    }
    //인접 그래프 초기화
    public void graphInit(int N, int[][] road){
        for(int i=0;i<N+1;i++){
            graph.add(new ArrayList<>());
        }

        for(int i=0;i<road.length;i++) {
            graph.get(road[i][0]).add(new int[]{road[i][1],road[i][2]});
            graph.get(road[i][1]).add(new int[]{road[i][0],road[i][2]});
        }
    }
}