Sho1007

MMORPG 클라이언트 개발자 지망생

1 minute read

3112. Minimum Time to Visit Disappearing Nodes / c++ / Medium / 1시간+

문제 및 코드

class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<int> answer = vector<int>(n, -1);
        answer[0] = 0;
        vector<vector<pair<int,int>>> adjVector = vector<vector<pair<int,int>>>(n);

        for (int i = 0; i < edges.size(); ++i)
        {
            adjVector[edges[i][0]].push_back({edges[i][1], edges[i][2]});
            adjVector[edges[i][1]].push_back({edges[i][0], edges[i][2]});
        }

        set<vector<int>> Set;
        Set.insert({0, 0});

        while (Set.empty() == false)
        {
            auto Iter = Set.begin();
            vector<int> Current = *Iter;
            Set.erase(Iter);

            for (auto Iter : adjVector[Current[1]])
            {
                int nextPos = Iter.first;
                int nextTime = Current[0] + Iter.second;
                if ((answer[nextPos] == -1 || answer[nextPos] > nextTime) &&
                disappear[nextPos] > nextTime)
                {
                    auto EraseTarget = Set.find({answer[nextPos], nextPos});
                    if (EraseTarget != Set.end())
                    {
                        Set.erase(EraseTarget);
                    }

                    answer[nextPos] = nextTime;
                    Set.insert({nextTime, nextPos});
                }
            }
        }

        return answer;
    }
};

접근 방식

그래프 / 다익스트라 / Set

  1. 0부터 모든 노드까지의 최소 거리를 봤을 때 바로 다익스트라가 떠올랐다.
  2. 이 문제엔 한가지 추가 조건이 있었는데, disappear[i]일 때, 해당 노드가 사라진다는 것이었다.
  3. 그래서 다익스트라를 갱신할 때 nextTime < disappear[nextPos] 조건을 추가해줬다. (다음 노드까지의 시간이 다음 노드가 사라질 시간보다 작을 때)
  4. n의 최대개수인 50000일 때 시간 초과가 났다.
  5. 그래서 보통 다익스트라를 사용할 때는 큐를 활용했었는데, 가장 거리가 짧은 노드를 먼저 갱신해야할 꺼같아서 우선순위 큐로 바꿔줬었다. 하지만 그래도 시간초과
  6. 고민하다 1시간이 넘었고 다른 사람들의 접근방법을 참고했는데, 그 중에 Set을 활용한 풀이가 눈에 띄었다.
  7. 항상 우선순위 큐를 쓸 때 고민했던 건데, 우선순위 큐에 이미 들어간 값이 새롭게 갱신됐을 때, 기존 값을 어떻게 삭제할지가 문제였다.
  8. 그런데 Set을 쓰게 되면, 기존값을 검색해서 삭제할 수 있고, 이 문제의 경우 {다음 노드까지의 최소거리, 다음 노드의 번호} 처럼 원소가 2개인 벡터로 Set을 만들면, 알아서 벡터의 첫 번째 원소 기준으로 정렬을 해주기때문에 우선순위 큐를 사용한 것 같은 효과를 낼 수 있었다.
  9. 그렇게 갱신되면 기존 값을 Set에서 제거해주며 진행했더니 통과되었다.

생각해 볼 점

  1. 항상 고민했었던, 우선순위 큐에서 갱신되버린 원소의 기존값을 삭제하는 문제를 Set을 활용해서 해결하는 방법을 배웠다.
  2. 그리고 원소 2개짜리인 컨테이너가 필요할 때 항상 pair를 썼었는데, vector를 써도 된다는 점을 새롭게 배웠다. (사실 당연히 둘 다 {1, 2} 이런식으로 선언할 수 있는건데, 이걸 왜 이제 깨달았을까..)

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

You may also enjoy