[프로그래머스 C++] 섬 연결하기

< 해설 >

개인적으로 오래 걸린 문제임 ㅠㅠ 길찾기 알고리즘 문제는 처음이라 개념을 찾아가면서 문제를 풀어야했다. 물론 기본적인 개념은 다 알고있지만 코드에 적용시키는건 다른 능력인것 같다는걸 또 한번 느낌 ㅠㅠ

 

최소신장 트리를 사용해야하는 문제이다.

신장트리란 방향이 정해지지 않은 트리이고 그 신장트리에서 최소 경로를 찾는게 핵심이다.

cost 값을 기준으로 정렬을 하는 것이 문제 풀이의 가장 기초적인 요소가 된다. 

 

크루스칼 알고리즘은 최소 신장 트리를 구하는 대표적인 알고리즘이다.

정렬된 데이터를 순회하면서 노드간 사이클이 발생했는지를 탐색하여 모든 노드를 돈다.

크루스칼 알고리즘을 한번도 사용해보지 않았기 때문에 크루스칼 알고리즘을 사용하여 풀려고 노력했다.

 

처음엔 노드간 선을 이을 때 두 노드가 이전에 방문한 적이 있는지를 생각해서 문제를 풀었다.

다음과 같은 경우에는 위의 방법으로 문제를 해결할 수 있다.

최소 cost의 간선을 이어도 그래프가 이어져 있다. 노드1 과 노드3 을 연결하려고 하면 노드3이 방문전이므로 연결 가능하다. 이 후 노드0과 노드3을 연결하려고 하면 0,3 모두 방문한 전적이 있으므로 연결하지 않는다.

 

하지만 다음과 같은 상황에서는 양 노드의 방문 기록을 봐서는 그래프가 정상적으로 이어지지 않는다.

위의 그림과 같은 그래프에서는 최소cost인 cost = 1 간선을 이으면 분리된 그래프 2개가 나오게 된다. 이 후 cost=5 짜리를 이은 후, 그래프를 완성시키기 위해서는 노드2 - 노드3 의 cost가 가장 작으므로 이어줘야 하지만, 노드2와 3 모두 방문한 적이 있는 상태이므로 둘은 연결되지 않는다.

 

따라서 노드2와 노드3 을 잇기 위해서는 선이 연결되어있는지의 여부를 따져야 사이클의 여부를 알 수 있게된다.

 

내가 푼 방법은 다음과 같다. 노드2를 시작으로, 노드3을 목적지로 둔다. 노드를 연결할 때에 vector에 

a노드 - b노드 와 b노드 - a노드 이렇게 두가지를 넣어준다. 그래서 노드 2가 시작이므로 vector[0]번에 있는 값이 노드2 인지를 탐색하여 어떤 노드와 연결되어있는지를 보고, 재귀함수를 사용하여 노드 2와 연결되어있는 노드를 기준노드로 바꿔서 탐색한다.

 

시간이 오래걸렸던 이유는 무한루프를 피하기 위해 어떤방식이 가장 효율적일지를 고민하느라 늦었던것 같다. 처음엔 방문한 노드를 vector에서 erase시켜줬는데 index로 접근하는 벡터에서의 erase는 위험하기도 하고 효율성도 떨어질것 같고 올바른 답도 나오지 않았다. 그래서 pair를 이용해서 연결된 노드에 추가적인 bool 값을 넣어주었다. bool 값이 false인 간선만 탐색하면 되므로 무한 루프를 피할 수 있게된다. 

 

시간은 오래걸렷지만 풀고나니 뿌듯한 문제같다! 다음 길찾기 문제들은 잘 풀수 있을 자신감도 생기고.. 피곤하지만 뿌듯하다 ^^..

 

< 문제 >

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.

다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

 

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

4

[[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]]

4

 

입출력 예 설명

costs를 그림으로 표현하면 다음과 같으며, 이때 초록색 경로로 연결하는 것이 가장 적은 비용으로 모두를 통행할 수 있도록 만드는 방법입니다.

 

< 풀이 >

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(vector<int> a, vector<int> b)
{
    if(a[2] >= b[2])
        return false;
    else
        return true;
}

bool isCycle(int StartNode, int DestNode, vector<pair<pair<int, int>, bool>> ConnectedNode)
{
    int curIDX = 0;

    while (curIDX < ConnectedNode.size())
    {
        if (!ConnectedNode[curIDX].second && ConnectedNode[curIDX].first.first == StartNode)
        {
            if (ConnectedNode[curIDX].first.second == DestNode)
                return true;
            else
            {
                pair<int, int> eraseNode = ConnectedNode[curIDX].first;
                ConnectedNode[curIDX].second = true;
                if (isCycle(eraseNode.second, DestNode, ConnectedNode))
                    return true;
            }
        }
        curIDX++;
    }
    
    return false;
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(), costs.end(), compare);
    vector<pair<pair<int, int>, bool>> ConnectedNode;

    for (int i = 0; i < costs.size(); i++)
    {
        // 사이클이 아니라면 연결. 맞다면 건너뜀
        if (!isCycle(costs[i][0] , costs[i][1] , ConnectedNode))
        {
            ConnectedNode.push_back(make_pair(make_pair(costs[i][0], costs[i][1]), false));
            ConnectedNode.push_back(make_pair(make_pair(costs[i][1], costs[i][0]), false));

            answer += costs[i][2];
        }
    }   
    
    return answer;
}