23.03.22. 풀었던 문제들

Leetcode 2492. Minimum Score of a Path Between Two Cities

첫 번째 접근

 2022 카카오 인턴 코딩테스트 4번 문제와 비슷하다. dijkstra를 하되, [지금까지 path + v->w weight]로 dijkstra하는 것이 아니라 [지금까지 path, v->w weight] 중 min값으로 dijkstra해야 한다.

// Runtime 560 ms Beats 39.70%
// Memory 130.3 MB Beats 58.31%

typedef pair<int, int> pii;

struct cmp{
    bool operator()(pii &a, pii &b){
        if(a.second == b.second) return a.first < b.first;
        return a.second > b.second;
    }
};

class Solution {
public:
    vector<vector<pii>> edges; // .first : 도착점, .second : weight
    vector<int> dists;
    priority_queue<pii, vector<pii>, cmp> pq; // .first : vertex, .second : weight
    int minScore(int n, vector<vector<int>>& roads) {
        // init
        edges.resize(n+1);
        dists.resize(n+1);
        fill(dists.begin(), dists.end(), INT_MAX);
        for(vector<int>& road : roads){
            edges[road[0]].push_back({road[1], road[2]});
            edges[road[1]].push_back({road[0], road[2]});
        }

        // dijkstra
        // dists[1] = 0; *** 실수 : 0으로 하면 전부 다 0이 됨
        pq.push({1, dists[1]}); 
        while(!pq.empty()){
            int curVertex = pq.top().first, curWeight = pq.top().second; pq.pop();

            for(pii edge : edges[curVertex]){
                int nextVertex = edge.first, nextWeight = edge.second;
                if(min(curWeight, nextWeight) < dists[nextVertex]){
                    dists[nextVertex] = min(curWeight, nextWeight);
                    pq.push({nextVertex, dists[nextVertex]});
                }
            }
        }

        return dists[n];
    }
};

시간복잡도

 이렇게 풀 경우 dijkstra의 시간복잡도이다. 따라서 O((V + E)logV)이다.

 

공간복잡도

 edge에 O(E), dist, pq에 O(V)가 들어간다. 따라서 O(V + E)

 

 

다른 접근

 solution을 보고 알았는데 dijkstra 말고 disjoint-set-union으로도 풀 수 있다.

 disjoint set으로 이 문제를 표현하면, [disjoint set의 edge 중 제일 작은 weight]가 해당 disjoint set의 모든 path의 weight이다. 또한, 문제에서 주어진 제한은 vertex 1과 n은 이어져 있는 것이 조건이기 때문에 1과 n은 무조건 같은 disjoint set에 존재한다는 것을 보장할 수 있다.

 따라서 disjoint set에 대해 min weight값을 찾는 것으로 목표를 바꿀 수 있다. (문제에서 주어진 예제 2번처럼) 그렇다면 union-find를 이용해 모든 edge에 대해 union하고, union할 때 해당 disjoint set에 있는 weight을 min값으로 설정하면 된다.

 마지막으로 1이나 n이 속해있는 disjoint set의 min값을 불러온다.

• path-compression을 사용해 union-find를 한다.
• 모든 edge에 대해 union한다.
  • union할 때 해당 disjoint set의 값을 min값으로 설정한다.
• 1이 속해있는 disjoint set의 min weight값을 리턴한다.

// Runtime 361 ms Beats 99.69%
// Memory 102.1 MB Beats 98%

class Solution {
public:
    vector<int> parents, answer;
    int Find(int n){
        if(n == parents[n]) return n;
        parents[n] = Find(parents[n]);
        return parents[n];
    }
    int minScore(int n, vector<vector<int>>& roads) {
        parents.resize(n+1);
        answer.resize(n+1);
        for(int i = 0; i<n+1; i++){
            parents[i] = i;
            answer[i] = INT_MAX;
        }

        for(vector<int> &road : roads){
            int rx = Find(road[0]), ry = Find(road[1]);
            parents[rx] = parents[ry];
            answer[rx] = answer[ry] = min(road[2], min(answer[rx], answer[ry]));
        }

        return answer[Find(1)];
    }
};

 

시간복잡도

 이렇게 풀 경우 총 path compression을 사용하므로 vertex 개수가 n, edge 개수가 m일 때 O(mlog*n)이다.

 

공간복잡도

 총 n size 배열만 사용하므로 O(n)이다.

 

후기

 이걸 disjoint set으로 풀 생각을 하다니.. 신박하다. 문제 제한조건으로 [1과 n은 무조건 같은 disjoint set에 있다]로 disjoint set을 채용하고, 이것으로 문제를 풀 수 있다는 게 신박했다. 나중에 다시 한 번 풀어봐야겠다.