글 읽기 - 유니온 파인드로 해결하려는데 막혀서 질문드립니다.

y_ht 3년 전 1

find와 unite함수의 형태는 유니온 파인드 문제마다 거의 유사해서 이 문제도 그렇게 시도했습니다.

저는 unordered_map<string, pair<string, int>> 형태로 맵을 선언해서 사용했습니다.

자세한 내용은 코드 주석을 참고해주세요.

구현상에 문제가 없는 것 같은데 오래 고민해도 틀린 이유를 찾지 못해서 질문을 드립니다.

#include <bits/stdc++.h>

using namespace std;

// 맵상에서 자신의이름 : <집합 최상위 이름, 집합의 크기> 형태로 저장된다.
unordered_map<string, pair<string, int>> mp;  

// 유니온 파인드로 해결하자. find 함수와 unite함수를 구현한다.

// 인자로 받아온 s가 속한 집합의 최상위 이름을 리턴함
string find(string s) {
    if (!mp.count(s)) {  // 맵에 이름이 없으면 새로 만든다.
        mp[s] = {s, 1};
        return s;
    }
    if (s == mp[s].first) return s;
    return mp[s].first = find(mp[s].first);  // 경로압축함
}

// s1, s2의 집합을 합친다. 합친 후 집합의 크기를 리턴함
int unite(string s1, string s2) {
    s1 = find(s1);
    s2 = find(s2);
    if (mp[s1].second < mp[s2].second) swap(s1, s2);
    mp[s1].second += mp[s2].second;
    mp[s2].first = s1;
    return mp[s1].second;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t, m;
    cin >> t;
    while (t--) {
        mp.clear();  // 각 테스트케이스 시작마다 맵을 비운다.
        cin >> m;
        string s1, s2;  // 입력으로 받을 사람 이름 2개
        while (m--) {
            cin >> s1 >> s2;
            cout << unite(s1, s2) << '\n';
        }
    }
}

3587jjh 3년 전 1

s1과 s2가 이미 같은 집합에 속해있는 경우가 고려가 안되어있네요

y_ht 3년 전 0

@3587jjh 감사합니다 덕분에 해결했습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

유니온 파인드로 해결하려는데 막혀서 질문드립니다.

y_ht 3년 전 1

3587jjh 3년 전 1

y_ht 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말