[2022 KAKAO TECH INTERNSHIP] 등산코스 정하기

[uijin-j]

🔗 등산코스 정하기

[hye-on]

• Language : C++
• 성능

코드 풀이

```cpp #include #include #include #include #include using namespace std; // 12:16 //다익스트라 // 산봉우리 여러개 어떻게 -? 산봉우리 하나마다 다익스트라? 50000개인데? -> 한번에 끝내기? #define MAX 10000001 vectordist(50001,MAX); //[i] i번째에서 봉우리에서 최대 intensity bool visit[50001]; vector>graph[50001]; //연결 저장 vector answer; setgates; setsummits; priority_queue>>q; //intensity , <봉우리, 현재 노드> // 다익스트라 -> 가장 비용이 적은(가중치가 작은) 노드 먼저 , 왜냐면 최소 경로를 찾기 떄문 // -> 경로의 비용은 intensity로 대체 // -> 더 작은 intensity를 가지고 그 노드를 방문할 일이 없다 void dijkstra(){ while(!q.empty()){ int d = -q.top().first; int sum = q.top().second.first; int cur = q.top().second.second; q.pop(); //문에 도착했다면 답을 갱신해주고(더 작다면) 탐색 끝 if(gates.find(cur)!=gates.end()){ dist[sum] = min(dist[sum],d); continue; } //방문한 노드는 방문 x if(visit[cur]) continue; visit[cur] =true; for(int i=0;idist[sum]) continue; q.push({-cost,{sum,node}}); } } } vector solution(int n, vector> paths, vector _gates, vector _summits) { answer.resize(2); answer[1] = 10000001; int a=0,b=0,w=0; for(int i=0;i

코멘트

- 우선순위큐를 사용안해서 오래걸렸네요. 원래 다익스트라는 각 노드까지 거리를 저장하는데 그러면 용량이 오버되서 (dist[50001][50001]) 어떻게 intensity를 저장할 수 있을까를 생각하는게 어려웠던것 같습니다. 시작노드가 여러개라..
- set 활용법 좀 까먹었었네요. find 기억하기..

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

```java import java.util.*; // 15:41 START! 16:27 END! (50분) class Solution { /** * 모든 산 봉우리에서 게이트로 가는 최소 intensity를 구하고 그 중에 최솟값을 리턴! => O(n * nlogn) ~= 2_500_000_000 애매하네.. * * 다익스트라와 비슷하게 최소 intensity를 구하지만, 거리가 아닌 intensity라는 점이 다름! */ public class Node { int node; int intensity; public Node(int node, int intensity) { this.node = node; this.intensity = intensity; } } List> graph; Set gateSet, summitSet; // 정상에서 탐색할 때, 다른 정상은 가면 안되고 게이트를 발견하면 탐색을 중단해야 하기 때문에 필요! public int[] solution(int n, int[][] paths, int[] gates, int[] summits) { int[] answer = new int[]{ 0, Integer.MAX_VALUE }; graph = new ArrayList<>(); for(int i = 0; i <= n; ++i) graph.add(new ArrayList<>()); for(int[] path : paths) { int n1 = path[0]; int n2 = path[1]; int time = path[2]; graph.get(n1).add(new Node(n2, time)); graph.get(n2).add(new Node(n1, time)); } gateSet = new HashSet<>(); for(int gate : gates) gateSet.add(gate); summitSet = new HashSet<>(); for(int summit : summits) summitSet.add(summit); for(int summit : summits) { int intensity = findBestIntensity(summit, n); // summit에서 any gate로 가는 최단 intensity if(intensity < answer[1]) { answer[0] = summit; answer[1] = intensity; } else if(intensity == answer[1]) answer[0] = Math.min(answer[0], summit); } return answer; } public int findBestIntensity(int summit, int n) { boolean[] check = new boolean[n+1]; PriorityQueue pq = new PriorityQueue<>((a, b) -> a.intensity - b.intensity); // intensity가 작은 애가 먼저 나옴! pq.offer(new Node(summit, 0)); while(!pq.isEmpty()) { Node node = pq.poll(); if(check[node.node]) continue; check[node.node] = true; if(gateSet.contains(node.node)) { return node.intensity; } for(Node next : graph.get(node.node)) { if(!check[next.node] && !summitSet.contains(next.node)) { pq.offer(new Node(next.node, Math.max(node.intensity, next.intensity))); } } } return Integer.MAX_VALUE; } } ```

코멘트

- 다익스트라 응용 문제 같네용! 시초가 날 것 같아서 확신없이 풀었지만, 그래도 풀렸습니다🥹
- 그래프 정보를 저장할 때, 처음에는 배열을 썼는데, n이 커지면 메모리 초과가 나더라구요! 메모리를 아끼기 위해 List로 변경했습니다!