[2022 KAKAO TECH INTERNSHIP] 등산코스 정하기
2024. 2. 13. 12:30ㆍCS/Algorism
https://school.programmers.co.kr/learn/courses/30/lessons/118669
- 출입구를 A, 산봉우리를 B라고 할 때, A -> ... -> B -> ... -> A의 경로로 이동한다. 그리고 가장 작은 intensity를 구하면 된다.
- 이때 출입구 A -> 산봉우리 B로 이동할 때의 최소 intensity만 구하면 된다.
- B -> A에서의 최소 intensity는 A -> B로 올라온 경로로 똑같이 내려가면 되기 때문이다.
- 이렇게 생각하면 별도의 중복 처리 없이 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 하는 규칙을 지킬 수 있다.
- 그리고 최소 intensity를 구해야 하는데 이때 사용되는 배열은 intensity[]이고 intensity[i]는 출입구에서 i까지 오를 때 intensity들 중 최댓값이다. 그리고 각각의 출입구에서 각각의 산봉우리까지 오르는데 intensity[B]의 최솟값을 구하면 된다. 이때 다익스트라로 다음과 같은 경우에 intensity 배열 값을 갱신해주면 된다.
- if(intensity[to] > max(intensity[from], from~to로의 intensity))
intensity[to] = max(intensity[from], from~to로의 intensity)
- if(intensity[to] > max(intensity[from], from~to로의 intensity))
- 그리고 처음에는 출입구마다 다익스트라를 진행해서 시작점 1에서 산봉우리들까지의 거리, 시작점 2에서 산봉우리들까지의 거리, .... 를 모두 계산했다. 그랬더니 시간 초과가 났다. 알고보니 그냥 시작점을 모두 큐에 넣어서 한 번만 다익스트라를 진행하면 된다. 어차피 각 산봉우리까지 걸리는 intensity의 최솟값만 구하면 되기 때문에 시작점이 어디였든지 간에 구분해줄 필요는 없는 거 같다.
- 마지막으로 주의할 점은 intensity가 최소가 되는 등산코스가 여러 개라면 그 중 산봉우리 번호가 가장 낮은 등산코스를 선택해야 한다는 점이다. 따라서 산봉우리 번호가 낮은 순으로 정렬해서 값을 도출해야 한다. 이 부분을 못 봐서 계속 틀렸는데.. 문제를 꼼꼼하게 잘 읽자!!!!!!!!
import java.util.*;
class Solution {
int n;
int[][] paths;
int[] gates;
int[] summits;
List<List<Node>> list = new ArrayList<>();
int[] dist;
public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
this.n = n;
this.paths = paths;
this.gates = gates;
this.summits = summits;
for (int i = 0; i <= n; i++) {
list.add(new ArrayList<>());
}
// 출입구 -> 정상으로의 최소 비용만 구하면 된다.
for (int[] path : paths) {
int v1 = path[0];
int v2 = path[1];
int intensity = path[2];
// 단방향
if (isGate(v1) || isSummit(v2)) {
list.get(v1).add(new Node(v2, intensity));
} else if (isSummit(v1) || isGate(v2)) {
list.get(v2).add(new Node(v1, intensity));
}
// 양방향
else {
list.get(v1).add(new Node(v2, intensity));
list.get(v2).add(new Node(v1, intensity));
}
}
dijkstra(); // 다익스트라
Arrays.sort(summits); // 산봉우리 번호가 낮은 순서대로 정렬
int minIntensity = Integer.MAX_VALUE;
int summitNum = 0;
for (int summit : summits) {
if (dist[summit] < minIntensity) {
minIntensity = dist[summit];
summitNum = summit;
}
}
return new int[]{summitNum, minIntensity};
}
private void dijkstra() {
PriorityQueue<Node> que = new PriorityQueue<>();
dist = new int[n + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
boolean[] visited = new boolean[n + 1];
// 시작점
for (int gate : gates) {
dist[gate] = 0;
que.add(new Node(gate, 0));
}
while (!que.isEmpty()) {
Node now = que.poll();
if (visited[now.end]) continue;
visited[now.end] = true;
for (Node node : list.get(now.end)) {
if (dist[node.end] > Math.max(dist[now.end], node.intensity)) {
dist[node.end] = Math.max(dist[now.end], node.intensity);
que.add(new Node(node.end, dist[node.end]));
}
}
}
}
private boolean isSummit(int v) {
for (int summit : summits) {
if (summit == v) {
return true;
}
}
return false;
}
private boolean isGate(int v) {
for (int gate : gates) {
if (gate == v) {
return true;
}
}
return false;
}
class Node implements Comparable<Node> {
int end, intensity;
public Node(int end, int intensity) {
this.end = end;
this.intensity = intensity;
}
@Override
public int compareTo(Node o) {
return intensity - o.intensity;
}
}
}
'CS > Algorism' 카테고리의 다른 글
[백준] 2493. 탑 (0) | 2024.02.29 |
---|---|
[2023 KAKAO BLIND RECRUITMENT] 개인정보 수집 유효기간 (0) | 2024.02.27 |
[백준] 2212. 센서 (1) | 2024.02.08 |
[백준] 1525. 퍼즐 (1) | 2024.02.06 |
[백준] 5014. 스타트링크 (1) | 2024.02.05 |