[백준] 4195번 : 친구 네트워크

문제

 

---

풀이

 

myunji.tistory.com/367

[백준] 1717번 : 집합의 표현

이 문제랑 거의 유사한데 다만 입력값이 string이라는게 조금 까다로울 뿐이다.

string으로 들어온 입력값을 int처럼 사용할 수 있게 map을 사용할 것이다.

 

Fred - 1

Barney - 2

Betty - 3

Wilma - 4

 

이런식으로 저장하면

parent[4]는 Wilma의 부모 노드인 뭐 그런거다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

map<string, int> m; //map을 사용해서 각 이름을 int처럼 사용
vector<int> parent;

int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
    if (parent[x] < 0)
        return x;
    return parent[x] = findParent(parent[x]);
}

int unionInput(int x, int y) { //union 한 뒤, 집합의 크기 리턴
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합
        return parent[x_p];
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
        return parent[x_p];
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
        return parent[y_p];
    }
}

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

    int T, F;
    string input[2];

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> F;
        parent.assign(2 * F + 1, -1); //F에 대해 들어올 수 있는 최대 인원 수
        int cnt = 1; //이름에 대한 인덱스
        for (int j = 0; j < F; j++) {
            cin >> input[0] >> input[1];
            for (int k = 0; k < 2; k++) { //map에 없으면 인덱스 추가
                if (m[input[k]] == 0)
                    m[input[k]] = cnt++;
            }
            cout << abs(unionInput(m[input[0]], m[input[1]])) << '\n'; //유니온 연산 후 집합의 크기 출력
        }
        m.clear(); //map 초기화
    }
}

전체 소스코드다.

 

        cin >> F;
        parent.assign(2 * F + 1, -1); //F에 대해 들어올 수 있는 최대 인원 수

입력으로 들어오는 친구가 총 몇명인지 문제에서 주어지진 않는다.

하지만 친구 관계인 F를 보면 대충 유추할 수 있다.

F=2라고 해보자. 그럼 입력으로 들어올 수 있는 최대 친구의 수는 4명이다.

 

A B

C D

이렇게 들어오는 경우다. 인덱스를 1부터 사용할거라 2*F를 하고 1을 더한만큼을 할당하자.

 

        int cnt = 1; //이름에 대한 인덱스
        for (int j = 0; j < F; j++) {
            cin >> input[0] >> input[1];
            for (int k = 0; k < 2; k++) { //map에 없으면 인덱스 추가
                if (m[input[k]] == 0)
                    m[input[k]] = cnt++;
            }
            cout << abs(unionInput(m[input[0]], m[input[1]])) << '\n'; //유니온 연산 후 집합의 크기 출력
        }

이제 각 이름에 대해 인덱스를 부여할 건데 cnt변수를 1로 초기화 해둔다.

그리고 만약 m[input[k]]가 0이라면 아직 m에 해당 이름이 존재하지 않는 것이다.

그러므로 해당 이름에 cnt값을 인덱스로 부여한다.

 

이렇게 들어온 input[0], input[1]에 대해 유니온 연산을 한다.

 

int unionInput(int x, int y) { //union 한 뒤, 집합의 크기 리턴
    int x_p = findParent(x); //x의 부모
    int y_p = findParent(y); //y의 부모

    if (x_p == y_p) //이미 같은 집합
        return parent[x_p];
    if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
        parent[x_p] += parent[y_p];
        parent[y_p] = x_p;
        return parent[x_p];
    } else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
        parent[y_p] += parent[x_p];
        parent[x_p] = y_p;
        return parent[y_p];
    }
}

파인드 함수는 1717번과 동일하니 생략하겠다.

이번에는 집합의 크기를 반환해야 하기 때문에 int 리턴을 하게 했다.

 

만약 x, y가 같은 집합이라면 둘 중에 아무거나 리턴하면 된다.

x_p가 root가 됐다면 parent[x_p]를 리턴하고 반대의 경우엔 parent[y_p]를 리턴한다.

 

            cout << abs(unionInput(m[input[0]], m[input[1]])) << '\n'; //유니온 연산 후 집합의 크기 출력

이 값은 음수이니 abs를 해줘야 한다.

 

        m.clear(); //map 초기화

테스트 케이스가 여러개 들어오니 각 테스트 케이스마다 map을 초기화 해줘야 한다.