문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/118669?
여러 출입구, 쉼터, 산봉우리로 왕복하는 코스 중에서 intensity가 최소인 것을 찾는 문제.
문제 핵심 및 풀이
왕복?
같은 출입구에서 시작하여 산봉우리를 찍고 다시 돌아오는 것이다
.그리고 갔던 길을 다시 가도 된다.
그래서 말이 출입구 - 산봉우리의 왕복이지, 사실상 편도로 계산해도 된다.
왜냐하면 최소의 intensity를 찾았다면, 그 경로 그대로 다시 내려오면 되니까..
예를 들어, 출입구가 1이고, 4번이 산봉우리라고 하자.1번 출입구에서 4번 산봉우리까지 도착하는데
줄일 수 있는 intensity가 3이라고 하면 어떤 경로 (1 - a - b - 4) 이런 식으로 있을 것이다.
내려올 때는 어떻게 하면 될까?
그냥 그대로 왔던 길 그대로 밟고 (4 - b - a - 1)로 반대로 내려가면 된다.
즉, 출발지점에서 봉우리까지 올라가는 데의 intensity만 구하면 된다는 것.
한 지점에서 다른 지점으로 가기
즉 해당 문제는 한 출발지점에서 다른 산봉우리까지 가는 경로 사이의 비용을 판단하는 것.
다익스트라 알고리즘으로 접근하였다.
(이 포스팅은 독자가 다익스트라 알고리즘을 알고 있다고 가정하고 서술한다.)
하지만 원래 다익스트라 알고리즘은
한 노드에서 다른 노드로 가는 최단 경로, 비용의 최소 합을 구하는 것이기 때문에
해당 문제에서는 다익스트라 알고리즘을 변형해야 한다.
각 노드의 최소 intensity를 저장하는 배열 dist를 만들어둔다.
여기서 이동하는 비용을 합해주는 것이 아닌, 기존의 비용과 이동하는 새로운 비용 중 더 큰 것으로 갱신해 주는 것이다.
이러한 반복을 통해 모든 출발점에서 모든 산봉우리까지 다익스트라를 해주면 된다.
실수하기 쉬운 부분
다익스트라 시간 및 메모리 초과
문제 제한 사항에서 노드(지점)의 개수 n이 최대 50,000개까지,
간선(paths)의 길이가 최대 200,000개까지인 점을 간과하면 안 된다.
다익스트라 알고리즘의 시간 복잡도는
우선순위큐로 구현했을 때 V * | E Log(V) | 다.
즉 해당 문제에서 50,000* 200,000*4 = 10^5 * 10^ = 10^10이다.
만약 거의 모든 노드가 출입구라면 다익스트라를 써도 시간초과가 난다.
그리고, 보통 다익스트라에서 최소 비용을 저장하는 배열은
출발 노드와 도착 노드를 표현하여 2차원으로 세우는 것이 보통이다.
근데 이 문제는 그렇게 하면 50000*50000이라 배열초과가 난다.
최소 intensity 중 하나
그래서 모든 출입구에서 다익스트라를 따로 시작하는 것이 아니라,
어차피 최소 intensity 하나만 구하면 되니까 이를 동시에 실행시키는 것으로 하면 된다고 생각했다.
우선순위 큐에 출발지점을 전부 넣은 채로 다익스트라를 시작한다.
그렇게 나온 intensity가 답이 된다.물론 이러한 방식을 채택했으니
최소 intensity 배열도 1차원으로 표현하면 된다.
테스트 25번
25번 케이스가 시간초과가 날 수도 있을 것이다.
C++은 안 날 수도 있는데 C#으로 하니 시간 초과가 나더라
여기서 한 번의 최적화가 더 들어가 줘야 한다.
다익스트라를 진행하면서 우선순위 큐에서 노드를 빼줄 것이다.
현재 정답으로 저장되어 있는 최소 intensity보다 그 노드의 비용이 크다면?
그렇다면 이후의 경로가 어떻게 됐던,
intensity는 무조건 현재 정답보다 크게 될 것이기 때문에 실행해 줄 필요가 없다.
즉, (현재 정답 intensity < 현재 intensity) pass
해주는 조건을 추가해 주면 된다는 소리이다.
자세한 것은 코드 구현 부분에서 설명하겠다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
vector<vector<int>> node[50001]; // 연결 노드 정보
int dist[50001] = {0,}; // 각 노드의 최소 intensity
bool isTop[50001] = {false,}; // 그 노드가 산봉우리인지 체크
vector<int> ans(2); // 정답 배열
// 다익스트라
void dijkstra(vector<int> gates){
// 우선순위 큐 intensity가 낮은게 가장 먼저 나오도록 설정
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
// 모든 출발지점 큐에 넣음
for(auto it : gates){
q.push({0,it}); // (intensity, 노드 번호)
dist[it] = 0; // 출발 지점 = 0
}
while(!q.empty()){
int x = q.top().second; // 현재 노드
int cost = q.top().first; // 노드에 저장된 intensity
q.pop();
// ans에 값이 있고 최소 intensity가 현재 노드의 intensity보다 작은 경우
if(ans[0] != -1 && ans[1] < cost) continue;
// 해당 노드가 산봉우리인 경우
if(isTop[x]){
// 답에 저장된 intensity보다 작은 경우
if(ans[0] == -1 || ans[1] > cost){
// 갱신
ans[0] = x;
ans[1] = cost;
}
// 답에 저장된 intensity랑 같은데, 번호가 빠른 경우 번호만 바꿔줌
else if(ans[1] == cost && ans[0] > x) ans[0] = x;
continue;
}
// 현재 노드와 연결된 모든 노드 탐색
for(int i = 0; i < node[x].size(); i++){
int next = node[x][i][0];
int nCost = node[x][i][1]; // 그 노드로 가는 비용
nCost = max(nCost,cost); // 둘중 더 높은 비용
// dist 배열에 저장된 비용보다 작은 경우
if(dist[next] == -1 || nCost < dist[next]){
// 갱신하고 큐에 넣음
dist[next] = nCost;
q.push({nCost,next});
}
}
}
}
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
for(auto it : summits) isTop[it] = true;
fill(dist,dist+50001,-1); // dist 배열을 -1로 초기화
ans[0] = -1;
ans[1] = -1;
// 노드 연결
for(int i = 0; i < paths.size(); i++){
int n1 = paths[i][0];
int n2 = paths[i][1];
int cost = paths[i][2];
node[n1].push_back({n2,cost});
node[n2].push_back({n1,cost});
}
dijkstra(gates);
return ans;
}↑
C# 구현 코드
↓
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
static int[] dist = new int[50001]; // 각 노드의 최소 intensity
static List<List<int>>[] node = new List<List<int>>[50001]; // 연결 노드 정보
static bool[] isTop = new bool[50001]; // 그 노드가 산봉우리인지 체크
static int[] ans = new int[2]{-1,-1}; // 정답 배열
// 정렬 기준
public class MyCompare : IComparer<List<int>>
{
// intensity 기준 내림차순 정렬
public int Compare(List<int> x, List<int> y)
{
if (x[0] == y[0]) return y[1]-x[1];
return y[0]-x[0];
}
}
public static void Dijkstra(int[] gates)
{
// 우선순위 큐가 없으므로 SortedSet으로 비슷하게 흉내냄
// intensity가 작을수록 앞으로 오도록 설정
SortedSet<List<int>> q = new SortedSet<List<int>>(new MyCompare());
// 모든 출발지점 큐에 넣음
foreach (int gate in gates)
{
q.Add(new List<int>() { 0, gate }); // (intensity, 번호)
dist[gate] = 0; //출발지점 = 0
}
while (q.Count > 0)
{
List<int> cnt = q.First(); // 가장 앞에 있는 것
q.Remove(cnt); // SortedSet 가장 앞에있는 원소 삭제
int x = cnt[1]; // 현재 노드
int cost = cnt[0]; // 그 노드에 저장된 intensity
// 비용이 현재 그 dist배열에 저장된 최소거리보다 크다면 패스
if (cost > dist[x]) continue;
// ans에 값이 있고 최소 intensity가 현재 노드의 intensity보다 작은 경우
if (ans[0] != -1 && ans[1] < cost) continue;
// 해당 노드가 산봉우리인 경우
if (isTop[x])
{
// 답에 저장된 Intensity보다 작은 경우
if(ans[0] == -1 || ans[1] > cost){
// 답 갱신
ans[0] = x;
ans[1] = cost;
}
// intensity는 같은데 번호가 더 빠른 경우
else if(ans[1] == cost && ans[0] > x) ans[0] = x;
continue;
}
// 현재 노드와 연결된 모든 노드 탐색
for (int i = 0; i < node[x].Count; i++)
{
int next = node[x][i][0];
int nCost = node[x][i][1]; // 그 노드로 가는 비용
// cost와 그 노드로 가는 비용 중 더 큰 것이 저장된 dist보다 작은 경우
if (dist[next] == -1 || Math.Max(cost, nCost) < dist[next])
{
// dist 갱신하고 q에 넣음
dist[next] = Math.Max(cost, nCost);
q.Add(new List<int>() { dist[next], next });
}
}
}
}
public int[] solution(int n, int[,] paths, int[] gates, int[] summits)
{
Array.Fill(dist, -1); // dist -1로 초기화
// 노드 초기화
for (int i = 0; i <= n; i++) node[i] = new List<List<int>>();
foreach (int summit in summits) isTop[summit] = true;
// 노드 연결
for (int i = 0; i < paths.GetLength(0); i++)
{
int n1 = paths[i, 0];
int n2 = paths[i, 1];
int cost = paths[i, 2];
node[n1].Add(new List<int>() { n2, cost });
node[n2].Add(new List<int>() { n1, cost });
}
Dijkstra(gates);
return ans;
}
}
그래서 SortedSet을 통해서 우선순위 큐를 비슷하게 흉내 내서 사용하도록 한다.
내가 생각하기에는 C#에서 우선순위 큐를 구현하는 방법 중에서는 가장 깔끔한 방법 같다.
그래서 IComparer 인터페이스를 구현하여 정렬 기준을 만들어서 해줬다.
↑
시행착오
처음에는 조건을 보지 않고 DFS로 구현했다가 시간초과가 뜨고 난 뒤, 답을 봤다.
다익스트라로 푸는 거였는데, 여기서 내가 유연성이 없다는 것을 알았다.
다익스트라를 생각하지 않았던 건 아니었는데,
다익스트라는 최소합을 구하는 것이기 때문에 적절하지 않다고 생각했다
.왜 변형해서 사용할 생각을 하지 않았을까?
그리고 C#이 우선순위큐가 없다는 사실을 처음 알았다.
그래서 우선순위 큐를 다른 자료구조로 구현하는데 고생했다..
엄청난 고생을 했다.그래도 공부는 많이 한 것 같다.
생활비..