[12978] 배달

✔ 배달

[프로그래머스 12978]

문제 분석하기

다익스트라 또는 플로이드-워셜을 통해 시작 마을에서 바로 도착 마을로,

또는 시작 마을에서 다른 마을을 거쳐 도착 마을로 시간 안에 배달할 수 있는지 확인

손으로 풀어보기

1. 마을은 노드로, 마을을 연결하고 있는 도로는 엣지로 나타냄
2. 마을 개수만큼 인접 리스트 배열의 크기를 설정하고 도로의 개수만큼 반복문을 돌면서 그래프를 리스트 배열에 저장
   • 이때 도로의 비용이 존재하므로 인접 리스트 배열의 자료형이 될 클래스를 선언
3. 다익스트라 알고리즘을 수행
   • 이때 타깃 노드의 최단 거리가 배달 시간보다 클 경우 배달이 불가능해짐
4. 배달이 가능한 마을의 개수를 반환

슈도코드 작성하기

N(마을의 개수)
road(도로 정보의 개수)
K(음식 배달이 가능한 시간)
answer(배달이 가능한 마을의 개수)
자료구조 선언하기(그래프 정보 저장, 최단 거리 저장, 노드 사용 여부 저장)
for(i -> 노드인 마을의 개수만큼) {
    그래프 정보를 저장하는 인접 리스트 초기화하기
}
for(-> 엣지인 도로의 개수만큼) {
    인접 리스트 배열에 엣지 정보를 저장하기
}
거리 배열은 충분히 큰 수로 초기화하기
방문 배열 초기화하기
시작점을 기준으로 다익스트라 수행
for(i -> 마을의 개수만큼) {
    if(최단 거리 배열이 K보다 작거나 같다면)
        answer 증가
}
answer 반환

다익스트라 함수 {
    시작점을 오름차순 우선순위 큐에 넣고 시작
    while(큐가 빌 때까지) {
        현재 선택된 노드가 방문된 적이 있는지 확인하기
        현재 노드를 방문 노드로 업데이트하기
        for(현재 선택 노드의 엣지 개수) {
            if(타깃 노드 방문 전 && 현재 선택 노드 최단 거리 + 비용 < 타깃 노드의 최단 거리) {
                타깃 노드 최단 거리 업데이트하기
                우선순위 큐에 타깃 노드 추가하기
            }
        }
    }
}

Node {
    targetNode(가리키는 노드), value(엣지의 가중치) 
    우선순위 큐 정렬 기준을 위해 compareTo 함수 구현하기
}

코드 구현하기

/**
 * 12978) 배달
 */
public class L024_12978 {
    // Node 클래스
    class Node implements Comparable<Node> {
        // targetNode(가리키는 노드)
        int targetNode;
        // value(엣지의 가중치)
        int value;

        Node(int targetNode, int value) {
            this.targetNode = targetNode;
            this.value = value;
        }

        // 우선순위 큐 정렬 기준을 위해 compareTo 함수 구현하기
        public int compareTo(Node o) {
            if (this.value > o.value)
                return 1;
            else
                return -1;
        }
    }

    // 자료구조 선언하기(그래프 정보 저장, 최단 거리 저장, 노드 사용 여부 저장)
    static ArrayList<Node>[] list;
    static int[] distance;
    static boolean[] visited;

    // N(마을의 개수)
    // road(도로 정보의 개수)
    // K(음식 배달이 가능한 시간)
    public int solution(int N, int[][] road, int K) {
        // answer(배달이 가능한 마을의 개수)
        int answer = 0;
        // 그래프 정보를 저장하는 인접 리스트 초기화하기
        list = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            list[i] = new ArrayList<Node>();
        }
        // 인접 리스트 배열에 엣지 정보를 저장하기
        for (int i = 0; i < road.length; i++) {
            int a = road[i][0];
            int b = road[i][1];
            int c = road[i][2];
            list[a].add(new Node(b, c));
            list[b].add(new Node(a, c));
        }
        // 거리 배열은 충분히 큰 수로 초기화하기
        distance = new int[N + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        // 방문 배열 초기화하기
        visited = new boolean[N + 1];
        // 시작점인 1번 마을을 기준으로 다익스트라 수행
        dijkstra(1);
        // 1번 마을부터 시작하여 N번 마을까지 배달 가능한지 확인
        for (int i = 1; i <= N; i++) {
            // 최단 거리 배열이 K보다 작거나 같다면
            if (distance[i] <= K)
                // answer 증가
                answer++;
        }
        // answer 반환
        return answer;
    }

    // 다익스트라 함수
    private void dijkstra(int start) {
        // 시작점을 오름차순 우선순위 큐에 넣고 시작
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        distance[start] = 0;
        // 큐가 빌 때까지
        while (!pq.isEmpty()) {
            // now(현재 선택된 노드의 전체 정보)
            Node now = pq.poll();
            // now_node(현재 선택된 노드가 가리키는 노드 정보)
            int now_node = now.targetNode;
            // now_node를 방문한 적이 없다면
            if (!visited[now_node]) {
                // now_node를 방문 노드로 업데이트하기
                visited[now_node] = true;
                // now_node와 연결된 엣지 개수만큼 탐색
                for (Node next : list[now_node]) {
                    // next_node(now_node와 연결된 노드가 가리키는 노드 정보)
                    int next_node = next.targetNode;
                    // next_node가 방문 전이며
                    // now_node 최단 거리 + value < next_node의 최단 거리라면
                    if (!visited[next_node] && distance[next_node] > distance[now_node] + next.value) {
                        // next_node 최단 거리 업데이트하기
                        distance[next_node] = distance[now_node] + next.value;
                        // 우선순위 큐에 타깃 노드 추가하기
                        pq.add(new Node(next_node, distance[next_node]));
                    }
                }
            }
        }
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L024_12978 solution = new L024_12978();

        int N = 5;
        int[][] road = { { 1, 2, 1 }, { 2, 3, 3 }, { 5, 2, 2 }, { 1, 4, 2 }, { 5, 3, 1 }, { 5, 4, 2 } };
        int K = 3;
        int result = solution.solution(N, road, K);

        System.out.println(result);
    }
}