[백준/C++] 14621 - 나만 안되는 연애

풀이 시간: 46m30s00

시간 복잡도: O(N + MlogM + MlogN) // 입력 + 정렬 + 부모노드찾기

공간 복잡도: O(N+M)

참고 자료: https://medium.com/@lifthus531/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C%EC%99%80-%EC%B5%9C%EC%86%8C-%EC%8B%A0%EC%9E%A5-%ED%8A%B8%EB%A6%AC-63053849b989

문제

입력

입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 

둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 

다음 M개의 줄에 u v d가 주어지며 u학교와 v학교가 연결되어 있으며 이 거리는 d임을 나타낸다. (1 ≤ u, v ≤ N) , (1 ≤ d ≤ 1,000)

출력

깽미가 만든 앱의 경로 길이를 출력한다. (모든 학교를 연결하는 경로가 없을 경우 -1을 출력한다.)

문제 풀이

본 문제를 크루스칼 알고리즘, Union-Find를 사용해 풀었다.

그냥 아래와 같이 부모 노드를 전부 초기화 해주고, 남초와 여초의 노드가 연결되어있을 때만 arr 배열에 추가해주도록 했다.

그리고 모든 연결 경로 중에서 최소 비용부터 더해주기 위한 정렬을 진행해준다.

 

그리고 연결된 각 노드드로가 비용이 저장된 arr 배열을 전체 돌면서, 노드를 하나씩 연결해준다.

 

우선 사이클인지 판단해야하는데, 이는 부모노드가 같은지 확인하는 함수이다. 만약 부모가 같은 경우에는 이미 연결되어있는 노드라는 뜻이므로 건너뛰어주면 된다.

그리고 사이클이 아닌경우엔, ans에 해당 경로 비용을 더해주고, 그 노드들의 부모를 하나로 합쳐주면 된다.

이때 부모를 합칠 때에는 편의상 더 작은 부모를 기준으로 합치도록 했다.

 

여기서 이제 마지막에 ans를 출력하면 되는데, 만약 사심 경로 ans가 0인 경우에는 모든 학교를 연결하는 경로가 없는 경우이므로 -1을 출력하면 된다.

...

라는 나의 잘못된 생각 때문에 답이 틀렸다.

"모든 학교를 연결하는 경로가 없다"는 것은 ans가 0이라는 뜻이 아니라, 노드 하나라도 연결이 되지 않았을 때를 의미하는 것이다. 

 

따라서 사이클인지 판단하는 if 문 내부에서 노드가 연결되었을 때 cnt 값을 하나씩 더해주고, 마지막에 cnt 값이 모든 노드들 즉, 시작 노드 제외하고 N - 1번 연결이 잘 되었는지 확인하여 ans 값을 출력할지 -1을 출력할지 결정해준다.

전체 코드

// MST, Kruskal algorithm, Union-Find
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, ans = 0;
int parent[1001] = { 0, };
char univ[1001] = { "", };
vector<pair<int, pair<int, int>>> arr;

// 부모노드 가져오기
int getParent(int node) {
    if (parent[node] == node) return node;
    else return getParent(parent[node]);
}

// 노드 연결, 더 작은 부모노드로 변경
void unionParent(int node1, int node2) {
    node1 = getParent(node1);
    node2 = getParent(node2);
    if (node1 < node2) parent[node2] = node1;
    else parent[node1] = node2;
}

// 사이클인지 판단
bool isCycle(int node1, int node2) {
    node1 = getParent(node1);
    node2 = getParent(node2);
    if (node1 == node2) return true;
    else return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) { parent[i] = i; cin >> univ[i]; } // 부모 노드 초기화
    for (int i = 0; i < M; ++i) {
        int u, v, d; cin >> u >> v >> d;
        if (univ[u] != univ[v]) arr.push_back({d, {u, v}}); // 남초-여초일 때만 연결
    }
    sort(arr.begin(), arr.end()); // 최소 비용부터 더해주기 위해 정렬
    int cnt = 0;
    for (int i = 0; i < arr.size(); ++i) {
        if (!isCycle(arr[i].second.first, arr[i].second.second)) {
            ans += arr[i].first; // 비용 추가
            unionParent(arr[i].second.first, arr[i].second.second); // 부모 합침
            cnt++; // 연결된 노드 개수
        }
    }
    // 모든 노드가 연결되었는지 확인
    if (cnt == N - 1) cout << ans;
    else cout << "-1";
    return 0;
}

 

https://www.acmicpc.net/problem/14621