문제 설명
입출력 예시
요약
1번 마을에서 출발해서 K 이하의 시간으로 배달 가능한 모든 마을의 개수 구하기
풀이
접근 방식
1. 방문 가능한 모든 경로 찾기
→ 간선의 가중치(소요 시간)와 도착 마을의 번호를 담는 객체 클래스(Node) 생성
→ graph라는 배열에 특정 마을의 인접한 마을의 Node리스트를 저장
→ 마을을 잇는 간선은 방향이 없기 때문에 반대의 경우도 함께 저장
2. 최소 비용으로 마을 방문하기
→ 다익스트라(dijkstra) 알고리즘을 통해 최소비용으로 방문하는 경우를 구한다.
3. 배달 가능한 마을의 개수 구하기
→ K 이하의 비용이 드는 마을의 개수를 카운팅해서 리턴
코드 리뷰
import java.util.*;
// 도착 지점의 번호와 간선의 가중치를 담는 Node 객체 클래스
class Node {
int index; // 도착 지점 번호
int cost; // 간선의 가중치
public Node(int index, int cost) {
this.index = index;
this.cost = cost;
}
}
class Solution {
int N, K;
ArrayList<Node>[] graph; // 모든 경로를 담을 graph 배열
public int dijkstra(int start) { // 다익스트라 알고리즘을 통해 최소 비용으로 방문
boolean[] visited = new boolean[N+1]; // 재방문 방지를 위한 visited 배열
int[] dist = new int[N+1]; // 방문시 필요한 비용을 담을 dist 배열
Arrays.fill(dist, Integer.MAX_VALUE); // 최초 비용은 MAX_VALUE로 설정
// 우선순위 큐를 활용해 간선의 가중치가 적은 순으로 디큐
// 우선순위를 비교하기 위해 Node 객체에 Comparable을 implements하고 compareTo() 메소드를 오버라이딩 해도 되고,
// 아래처럼 람다식으로 Comparator의 compare() 메소드의 리턴값을 표기해도 됨
PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);
pq.add(new Node(start, 0)); // 처음 큐에 담을 객체는 시작 마을의 번호(= start)와 시작 마을의 가중치(=0)
dist[start] = 0; // 시작 마을까지의 거리는 0으로 초기화
while(!pq.isEmpty()) {
int now = pq.poll().index; // 우선순위 큐이기 때문에 가중치가 낮은 순으로 디큐됨
if(visited[now]) continue; // 방문한 마을이라면 건너 뛰고
visited[now] = true; // 방문했음을 표시
// graph에는 인접 노드의 정보가 담겨 있음(now가 1이라면 graph[1]에는 1번 마을에 대한 인접 마을의 번호와 각 간선의 가중치를 담은 Node 리스트가 있음)
for(Node adj : graph[now]) { // Node adj에는 인접 마을의 정보를 담은 Node 객체가 담김
dist[adj.index] = Math.min(dist[adj.index], dist[now] + adj.cost); // 인접 마을까지의 거리(dist)를 최소 비용으로 설정
pq.add(new Node(adj.index, dist[adj.index])); // 최소 비용으로 새롭게 갱신된 인접 마을에 대한 정보를 담은 Node 객체를 우선순위 큐에 추가
}
}
return (int)Arrays.stream(dist).filter(k -> k <= K).count(); // K이하의 비용으로 방문할 수 있는 마을의 개수 카운팅
}
public int solution(int N, int[][] road, int K) {
this.N = N;
this.K = K;
graph = new ArrayList[N+1]; // graph 배열 크기를 전체 마을의 개수 + 1 로 설정
for(int i = 0; i < graph.length; i++) {
graph[i] = new ArrayList<>(); // graph의 각 인덱스를 new ArrayList로 초기화
}
for(int[] arr : road) {
int u = arr[0]; // 출발지
int v = arr[1]; // 도착지
int cost = arr[2]; // 간선의 가중치
graph[u].add(new Node(v, cost)); // u마을의 인접 마을로 v 마을 번호와 간선의 가중치를 담는다.
graph[v].add(new Node(u, cost)); // v마을의 인접 마을로 u 마을 번호와 간선의 가중치를 담는다.
}
return dijkstra(1); // 다익스트라 알고리즘 실행
}
}
추가 자료
다익스트라 알고리즘 실행 순서
출력 로그와 함께 보기
시작 노드 : 1번
<1번 노드>를 방문합니다.
인접 노드 = 2, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 1
인접 노드 = 4, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 2
<2번 노드>를 방문합니다.
인접 노드 = 1, 시작 노드(1번)부터 해당 노드까지의 거리 = 0
현재 시작 노드(1번)부터 1번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 3, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 4
인접 노드 = 5, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 3
<4번 노드>를 방문합니다.
인접 노드 = 1, 시작 노드(1번)부터 해당 노드까지의 거리 = 0
현재 시작 노드(1번)부터 1번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 5, 시작 노드(1번)부터 해당 노드까지의 거리 = 3
현재 시작 노드(1번)부터 5번 노드까지는 최단 거리이므로 갱신하지 않습니다.
<5번 노드>를 방문합니다.
인접 노드 = 2, 시작 노드(1번)부터 해당 노드까지의 거리 = 1
현재 시작 노드(1번)부터 2번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 3, 시작 노드(1번)부터 해당 노드까지의 거리 = 4
현재 시작 노드(1번)부터 3번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 4, 시작 노드(1번)부터 해당 노드까지의 거리 = 2
현재 시작 노드(1번)부터 4번 노드까지는 최단 거리이므로 갱신하지 않습니다.
<3번 노드>를 방문합니다.
인접 노드 = 2, 시작 노드(1번)부터 해당 노드까지의 거리 = 1
현재 시작 노드(1번)부터 2번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 5, 시작 노드(1번)부터 해당 노드까지의 거리 = 3
현재 시작 노드(1번)부터 5번 노드까지는 최단 거리이므로 갱신하지 않습니다.
dist[] 배열을 index = 1부터 출력합니다.
dist[] = {0, 1, 4, 2, 3}
'알고리즘 > PROGRAMMERS' 카테고리의 다른 글
미로 탈출(Lv.2) (1) | 2024.04.16 |
---|---|
줄 서는 방법(Lv.2) (0) | 2024.04.15 |
대충 만든 자판(Lv.1) (0) | 2024.04.11 |
상품을 구매한 회원 비율 구하기(DB) (1) | 2024.03.28 |
n진수 게임(Lv.2) (1) | 2024.03.28 |