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

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

코딩테스트 연습 - 배달

---

문제

도로의 정보(2차원배열), N(노드의 개수), K(거리)가 주어진다

도로의 정보에는 각 노드-노드 (거리)의 정보가 들어있다

N=5이면 1,2,3,4,5라는 도시가 있고

도로의 정보가 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]이면,

1-2도시의 거리는 1, 

2-3도시의 거리는 3.. 이다

문제는 다음과 같다

1번 도시에서 시작해서 거리의 합이 K이하만 배달할 수 있다.

그러면 총 배달할 수 있는 마을의 수가 몇 개인지 구하는 문제이다

 

해결

dijkstra 문제이다

그래프 우선순위큐를 이용하여 풀었다
도착점 노드와 거리 필드를 가진 Edge를 구현하여 거리를 가중치로 가지도록 한다
방향이 없는 엣지를 가진 그래프를 정의, dist[] 배열에는 최단거리를 가지는데 초기값으로 Integer 최대값으로 셋팅
가장 처음에 1부터 시작하므로 도착노드 1, 거리 0인 엣지를 정의하여 우선순위 큐에 넣는다
BFS 탐색을 한다
- 현재 꺼낸 노드의 최단거리(dist[cur])가 현재 거리보다 작으면 continue
(왜냐하면 현재거리 + 다음거리가 최단거리면 업데이트인데, 이미 현재 거리보다 작으니 더 이상 수행을 하지 않아도 됨)
- 현재 거리보다 크면, 다음 노드의 거리와 현재 노드의 거리의 합이 최소인 것을 찾아서 dist[]에 에 업데이트 해주고, 큐에 넣어줌
최종적으로 dist[] 배열에는 각 노드에 도달하기까지의 최단거리가 나올 것이고,
다시한번, dist[] 배열을 돌면서 k이하일 때 count++하여 count를 출력한다

 

public class programmers_배달_js {

    static class Graph {

        private final List<List<Edge>> graph;

        public Graph(int nodeSize) {
            graph = new ArrayList<>();
            for (int i=1; i<=nodeSize; i++) graph.add(new LinkedList<>());
        }

        public void addDirectionlessEdge(int node1, int node2, int distance) {
            graph.get(node1).add(new Edge(node2, distance));
            graph.get(node2).add(new Edge(node1, distance));
        }

        public void dijkstra(int s, int[] dist) {
            dist[s] = 0;
            PriorityQueue<Edge> priorityQueue = new PriorityQueue();
            priorityQueue.offer(new Edge(s,0));

            while (!priorityQueue.isEmpty()) {
                Edge curEdge = priorityQueue.poll();

                int curDestination = curEdge.destination;
                int curDistance = curEdge.distance;

                if (dist[curDestination] < curDistance) continue;


                List<Edge> nextEdge = graph.get(curDestination);
                for (int i=0; i<nextEdge.size(); i++) {
                    int nextDestination = nextEdge.get(i).destination;
                    int nextDistance = nextEdge.get(i).distance;

                    if (dist[nextDestination] >= curDistance + nextDistance) {
                        dist[nextDestination] = curDistance + nextDistance;
                        priorityQueue.offer(new Edge(nextDestination, dist[nextDestination]));
                    }
                }
            }

        }
    }

    static class Edge implements Comparable<Edge> {

        int destination;
        int distance;

        public Edge(int destination, int distance) {
            this.destination = destination;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.distance, o.distance); // 오름차순
        }
    }
}