728x90
⬛ 프로그래머스 | LV.2 배달 - 다익스트라 문풀 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/12978
💚문제 접근 방식
문제를 읽으면서 다익스트라 문제라고 판단했다.
시작점은 1번 정점으로 항상 고정되어 있고, 다른 모든 정점으로의 최단거리로 배달했을 때 그 거리가 K이하인 경우 배달 가능으로 판단하여 개수를 리턴하라는 문제이다.
1) Edge 클래스, distance[] 배열, graph 리스트를 선언했다.
2) road 2차원 배열을 순회하면서 graph에 양방향 간선을 세팅해줬다.
3) 다익스트라를 호출한다.
- distance는 N+1까지 MAX값으로 초기화
- pQ 선언하여 초기값 담고, distance[s] = 0 세팅해준다.
- while로 pQ 빌 때까지 순회하면서 매번 현재 좌표를 경유한 거리가 기존의 nx distance값보다 작을 때마다 갱신하고 pQ에 담아주면서 순회를 한다.
- 이후 더 이상 갱신할 최소거리가 없을 때 while을 탈출한다.
- for문으로 distance 순회하면서 k이하 거리를 갖는 애들을 ++처리하여 반환해준다.
4) 반환한 값이 최종 정답이 된다.
💚 제출 코드
import java.util.*;
class Edge implements Comparable<Edge>{
int e, v;
Edge(int e, int v){
this.e = e;
this.v =v;
}
public int compareTo(Edge o){
return this.v- o.v;
}
}
class Solution {
static int[] distance;
static List<List<Edge>> graph;
//다익스트라 함수
public static int dijkstra(int s, int k){
Arrays.fill(distance, Integer.MAX_VALUE);
distance[s] = 0;
PriorityQueue<Edge> pQ = new PriorityQueue<>();
pQ.offer(new Edge(s, 0));
while(!pQ.isEmpty()){
Edge cur = pQ.poll();
if(cur.v > distance[cur.e]) continue;
for(Edge nx : graph.get(cur.e)){
if(distance[nx.e] > distance[cur.e] + nx.v){
distance[nx.e] = distance[cur.e] + nx.v;
pQ.offer(new Edge(nx.e, distance[nx.e]));
}
}
}
int ans = 0;
for(int i=1; i<distance.length; i++){
if(distance[i] > k) ans++;
}
return distance.length-1-ans;
}
//솔루션 함수
public int solution(int N, int[][] road, int K) {
int answer = 0;
graph = new ArrayList<>();
for(int i=0; i<=N; i++){
graph.add(new ArrayList<>());
}
distance = new int[N+1];
for(int[] x :road){
//양방향 간선
int a = x[0];
int b = x[1];
int v = x[2];
graph.get(a).add(new Edge(b, v));
graph.get(b).add(new Edge(a, v));
}
answer = dijkstra(1, K);
return answer;
}
}
728x90
'코딩 테스트 [준비] > [문풀] 프로그래머스_문풀_조지기' 카테고리의 다른 글
프로그래머스 | LV.2 호텔 대실 - 구현 문풀 (Java) (1) | 2024.04.01 |
---|---|
프로그래머스 | LV.2 테이블 해시 함수 - 구현 문풀 (Java) (0) | 2024.04.01 |
프로그래머스 | LV.2 하노이의 탑 - 재귀 문풀 (Java) (25) | 2024.03.29 |
프로그래머스 | LV.2 연도 별 평균 미세먼지 농도 조회하기 (MySQL) (22) | 2024.03.28 |
프로그래머스 (카카오) | LV.2 [3차] 방금그곡 - 구현 문풀 (Java) (22) | 2024.03.28 |