최소값, 모두 연결되어 있다.-> 백트래킹으로 진행함.

최소비용을 구해야하기 때문에 모든 경우에 대해서 탐색을 해야겠다는 생각을 해서 백트래킹을 생각함.

• 작성한 코드이고,
  

반례가 있다.

: dfs의 한계점

• dfs로 한곳만 집중적으로 방문하는데, 아래의 반례 처리 못한다.
  -> 부채꼴 형태의 그래프의 경우는 절대 풀 수 없다.
  

• 실행 결과
  

여행경로 문제와 비교.

• 여행경로의 조건을 보면,
  

• 이러한 경우는 없다. 는 것을 증명할 수 있고, 여기서는 dfs 로 풀 수 있다.
  -> a-> b, a->c

결론

결론
: 한붓그리기의 취약점을 발견했다..

---

한붓 그리기의 약점.

---

어떻게 할 건가?

일단 구글링

생각지도 못함.

• 유니온 파인드는 부모를 찾는 알고리즘으로만 생각했지만,
  다른 곳에서도 응용 됨.

최종 구글링 내용

• 섬 연결하기 dfs 목록에 있다.

두잇 자료구조 책에 자세하게 작성함.

---

문제 풀이 전략

• 왜 크루스칼인가?

유니온 파인드를 언제 사용?

• 크루스칼 알고리즘이고, 최소비용으로 모든 노드를 연결하라.
  -> 순환구조가 아니다.
  --> 순환구조를 확인할 수 있는 방법은 부모를 확인하는 방법으로 할 수 있다.
  => 유니온 파인드를 사용하자.

간선중에서 연결된 2개의 정점이 무엇이든 중요하지 않다.
아래의 0-1-2 순환 쪽을 보면, 비용이 5인 간선보다는 1과 2 비용의 간선을 선택하는 것이 0-1-2 번 노드를 연결하는데의 최소비용이다.

-> 여기서 유니온 파인드를 사용하자!

최종 코드

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

using namespace std;


struct Edge
{
    int startV;
    int endV;
    int cost;
    
    // 2개의 연결된 정점에 무관하게 
    // 가장 낮은 cost 가중치대로 정렬하자.
    
    bool operator<(Edge & e)
    {
        return cost < e.cost;
    }
    
};


// 경로 압축해야 함.

int parentV[101];

int Find(int vvalue)
{
    if(parentV[vvalue] == vvalue)
        return vvalue;
 
    return parentV[vvalue] = Find(parentV[vvalue]);   
}

void Union(int a, int b)
{
    int pA = Find(a);
    int pB = Find(b);
    
    if(pA < pB)
    {
        parentV[pB] = pA;            
    }
    else if(pA > pB)
        parentV[pA] = pB;             
}




int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    
    // 1. 최소비용으로 모든 섬을 통행가능하게
        // -> 순환구조를 만들 필요가 없다! 
    // 2. 어떤 간선을 선택하면서 최고의 간선을 선택할까?
    
    // 3. 문제를 전부 읽어보면, 그래프는 일직선 형태가 아니라
        // 그물형일 수 있다.
        
    // 간선을 기준으로 해서 진행하자. 
    
    vector<Edge> edges;
    
    for(auto iter : costs)
    {
        int sV = iter[0];
        int eV = iter[1];
        int cost = iter[2];
        
        edges.push_back({sV, eV, cost});
    }
    
    sort(edges.begin(), edges.end());
    
    // 크루스칼이므로, 유니온 파인드 개념을 가지고 와야 함. 
    
    for(int i = 0; i < 101; ++i)
    {
        parentV[i] = i;
    }
    
    // 오름차순으로 정렬된 edges를 가지고 진행하자. 
    
    for(auto iter : edges)
    {
        int sV = iter.startV;
        int eV = iter.endV;
        int cost = iter.cost;
        
        if(Find(sV) != Find(eV))
        {
            Union(sV, eV);
            answer += cost;
        }
      
    }
    
    
    
    return answer;
}