Sho1007

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

2 minute read

2662. Minimum Cost of a Path With Special Roads / c++ / Medium / 2시간+

문제 및 코드

inline int GetCost(int startX, int startY, int targetX, int targetY)
{
    return abs(startX - targetX) + abs(startY - targetY);
}
class Solution {
public:
    int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
        int n = specialRoads.size();
        vector<int> dp = vector<int>(specialRoads.size(), numeric_limits<int>::max());
        set<vector<int>> Set;
        for (int i = 0; i < n; ++i)
        {
            dp[i] = GetCost(start[0], start[1], specialRoads[i][0], specialRoads[i][1]) + specialRoads[i][4];
            Set.insert({dp[i], i});
        }

        while (Set.size())
        {
            auto iter = Set.begin();
            int cost = (*iter)[0];
            int pos = (*iter)[1];

            Set.erase(iter);

            if (dp[pos] != cost) continue;
            for (int i = 0; i < n; ++i)
            {
                
                if (i == pos) continue;
                int nextCost = GetCost(specialRoads[pos][2], specialRoads[pos][3], specialRoads[i][0], specialRoads[i][1]) + specialRoads[i][4] + cost;
                if (nextCost < dp[i])
                {
                    dp[i] = nextCost;
                    Set.insert({nextCost, i});
                }
            }
        }

        int answer = GetCost(start[0], start[1], target[0], target[1]);
        for (int i = 0; i < n; ++i)
        {
            
            answer = min(answer, dp[i] + GetCost(specialRoads[i][2], specialRoads[i][3], target[0], target[1]));
        }

        return answer;
    }
};

접근 방식

다익스트라 / Set

  1. fromX, fromY 지점부터 toX, toY 까지의 거리가 abs(fromX - toX) + abs(fromY - toY) 이고, 특정 fromPostion, toPosition, cost들 가지는 specialRoad가 있을 때, startX,startY 로부터 targetX, targetY 까지의 최단 거리를 구하는 문제
  2. 처음 생각한 방식은 start부터 target까지의 거리를 구할 때, specialRoad 를 순회하면서 임의의 원소를 road를 사용한다고 가정하고, start로부터 road의 시작점까지의 거리 + road 자체의 비용 + raod 끝점부터 target까지의 거리로 나눠서 최소값을 갱신하고, 다시 (start부터 road의 시작점까지)와 (road의 끝점부터 target까지)를 재귀적으로 2번 로직을 호출하면 되지 않을까? 였다.
  3. 하지만 이렇게 작성하니 stack overflow가 떴다. 역시나 재귀는 깊이가 깊어지면 사용이 불가능했다.
  4. 방법을 찾지 못해서 다른 사람들의 접근 방법을 봤다.
  5. 다익스트라를 써서 계속 비용을 최소로 갱신을 하신 식이었다.
  6. 생각해보니 노드에서 노드로 이동할 때 cost가 드는건 다익스트라를 쓸 생각을 했었는데, 이렇게 좌표값으로 주어질 때에는 다익스트라를 써볼 생각을 못했었다. (Cost 구하는 공식이 떡하니 있는데도..)
  7. start부터 specialRoads[i]의 끝지점까지의 최소 비용을 저장하는 배열 dp[i]를 선언하고, 우선 기본 비용으로 갱신해준 다음 Set에 넣어준다.. (거리차 공식으로 측정한 비용, 이제는 PQ대신 Set을 활용하는 것으로 바꿨다.)
  8. 다음 Set이 빌 때까지 반복
    1. Set의 가장 앞 원소 ([0]번 원소를 비용으로 뒀기 때문에, 비용이 가장 적은 원소)를 꺼낸다. 그 후 Set에서 지운다. (PQ.top(), PQ.pop()과 동일)
    2. 원소를 가지고 cost와 pos로 나눠서 저장
    3. dp[pos]가 cost가 아니라면 continue (이전 문제에서도 PQ에 원소가 새롭게 갱신됐을 때의 문제를 Set의 erase로 해결했었는데, 여기서는 항상 갱신된 최소값이 dp[i]에 저장되어 있기 때문에 이것을 활용했다.)
    4. 다음 specialRoads를 순회하면서, 현재 speicalRoads[pos]의 끝지점부터 specialRoads[i]의 시작지점까지의 비용 + specialRoads[i]의 비용 + cost 를 계산해서 만약 그게 dp[i]보다 작다면, dp[i]를 갱신하고, {dp[i], i} 를 다시 Set에 넣어준다. (다익스트라에서 경로를 갱신하고 갱신된 노드를 다시 PQ에 넣어주는 것과 동일)
  9. 8번을 마치고 나면, dp[i]에는 speicalRoads[i]를 사용했을 때의 최소 비용이 저장된다.
  10. 그럼 다시 dp를 순회하면서 dp[i] + speicalRoads[i]의 끝지점에서 target까지의 비용을 계산해서 그 중 최소값으로 answer를 갱신해준다.
  11. answer를 반환, 해결

생각해 볼 점

  1. index만 존재하는 node가 아니라 좌표값으로 다익스트라를 적용해 볼 수 있는 좋은 경험이었다. (물론 스스로 생각해내지는 못했지만)
  2. dp가 항상 약했었는데, 거기에 Heap까지 더해지니까 정신을 못차리고 풀이 방법을 빨리 파악해내지 못했었다. Heap 쪽을 좀 더 많이 풀어봐야겠다.
  3. 이제 내일이면 99클럽 2기가 끝나게 된다. 99클럽을 진행하면서 꾸준히 하루에 한문제씩을 풀 수 있었고, 덕분에 최근에 코테를 볼 일이 많았는데 불안함 없이 편하게 볼 수 있었던 것 같다. 99클럽 3기가 시작되면 또 신청해야겠다. (코테는 항상 준비하고 취미처럼 꾸준히 풀어야 실력이 녹슬지 않고 계속 발전할 수 있는 것 같다.)

해시태그

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

You may also enjoy