[프로그래머스]Lv.2 배달 (Java)

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

프로그래머스

 

문제 설명

각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있다. 각 마을은 양방향으로 통행할 수 있다.

도로를 지날 때 걸리는 시간은 도로별로 주어진다.

현재 1번 마을 음식점에서 각 마을로 음식배달을 하려고 한다.(1번 마을 포함)

각 마을로 주문을 받으려고 하는데, N개의 마을 중에서 K시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 한다. 

 

예를 들어, N=5, K=3인 경우이다.

위 그림에서 1번 마을 음식점은 [1, 2, 4, 5] 마을까지는 3 이하의 시간에 배달할 수 있다. 

따라서 1번 마을에서 배달주문을 받는 마을은 4개가 된다.

 

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달 가능한 시간 K가 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하시오.

---

💡 아이디어

각 마을이 연결된 노드 형식으로 주어지고, 해당 마을에 방문할 수 있는지(K시간 이내)를 묻는 문제이므로 DFS 방식으로 해결했습니다. 평소와 다른 점은 도로마다 시간이 따로 주어진다는 것인데, 해당 부분은 ArrayList를 int배열로 만들어주는 걸로 해결했습니다.

 

📗 풀이과정

1. 평소에는 map을 저장할 때는 a와 연결된 노드들을 넣는 ArrayList <Integer> 형식으로 구현해 방문할 수 있는 노드들만 저장해 사용하는 방식이었지만, int [] 형으로 [연결된 노드, 걸리는 시간]을 함께 넣어줍니다.

2. DFS(Depth-First Search)를 통해 1번과 연결된 마을을 탐색합니다.

 

3. 1번 마을에서부터 탐색을 시작하고, 1번 마을과 연결되어 있는 마을을 조사하는데 다음과 같은 조건을 만족하는 마을로 넘어갈 수 있도록 합니다.

1. 연결된 마을까지의 시간이 K를 넘지 않는 마을인지

2. 이전에 방문한 적이 없거나, 방문한 적이 있다면 그때보다 적은 시간이 걸리는 도로를 선택한다.

 

4. 1번에서 K시간 안에 갈 수 있는 도시들을 모두 구할 때까지 DFS를 반복하고, 조사가 끝나면 배달가능한 마을 개수를 반환합니다.

---

전체 코드

import java.util.*;
class Solution {
    static Map<Integer,ArrayList<int[]>> map = new HashMap<>();//전체 맵
    static Map<Integer,Integer> canGo = new HashMap<>();//visited_걸린시간
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        for(int i=1;i<=N;i++) map.put(i,new ArrayList<>());
        
        for(int i=0;i<road.length;i++){
            map.get(road[i][0]).add(new int[]{road[i][1],road[i][2]});//연결도로 + 걸리는 시간 저장
            map.get(road[i][1]).add(new int[]{road[i][0],road[i][2]});
        }
        dfs(1,0,K);

        return canGo.size();
    }
    //현재 위치, 현재 위치까지 걸린 시간, K
    void dfs(int now, int time, int maxTime){
        //System.out.println(now);
        canGo.put(now,time);//now마을을 time시간에 걸려서 배달가능하다고 저장.
        
        for(int[] r : map.get(now)){
            //시간이 K를 넘지 않고, 이전에 방문한적이 없거나 방문한 적이 있으면 그때 시간보다 짧을 때 다시 방문
            if(time+r[1]<=maxTime && (!canGo.containsKey(r[0]) || time+r[1]<canGo.get(r[0])))
                dfs(r[0],time+r[1],maxTime);
        }
    }
}