4195번: 친구 네트워크 [JAVA]

문제 설명

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

4195번: 친구 네트워크

[문제]

 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

 

[입력]

 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다. 친구 관계는 두 사용자의 아이디로 이루어져 있으며, 알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

 

[출력]

 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

 

[예제 입력 1]

2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

[예제 출력 1]

2
3
4
2
2
4

---

풀이

 문제를 보았을 때는 쉽게 union-find 관련 문제임을 파악할 수 있다. 다만 단순히 최상단 노드를 찾기만 하면 되는 여타 다른 문제와는 약간 다르게 문제 요구 상 집합의 사이즈도 연산을 할 수 있어야 한다.

 문제 해결을 쉽게 하기 위해선 우선 String으로 들어올 이름에 대해 알고리즘 상 쉽게 다룰 수 있도록 int 타입으로 인덱스화를 해준다. 이후 일대일 대응으로 이루어진 인덱스들로 union-find 연산을 해주는 데, 이 때 각 집합의 사이즈를 미리 저장해두었다가 두 집합의 merge를 진행할 때 크기도 같이 합해주면 된다. 예를 들어 merge를 진행하는 두 집합의 최상단 노드 A, B에 대해 A의 부모를 B로 지정해주면서 집합 B의 크기를 A와 B의 합으로 초기화를 해주는 방식이다.

 이를 문제 입력에 적용하여, 한 줄을 통해 입력 받는 두 이름 A, B에 대해 이들이 기존에 없던 이름이면 인덱스화를, 또는 기존에 있던 이름이라면 그 이름이 속한 그룹의 최상단 인덱스(노드)를 찾아 반환한다. 이후 2개에 대해 merge를 진행하면 되는 것이다. 그리고 그 집합의 크기를 답에 저장하면 된다.

 여담으로 문제를 통과하는 데는 한 가지가 더 필요했는데, 바로 최상단 노드를 찾는 함수의 개선이다. 기존에는 단순히 목적에만 충실히 while 문을 통해 최상단 노드를 찾아 반환했는데, 이러한 경우 구조가 복잡해질수록 while문을 많이 돌 수가 있다. 이를 해결하기 위해 함수를 재귀호출로 변환하면서 답이 반환될 때 특정 노드의 부모 노드를 동시에 최상단 노드로 초기화하여, 이후 그 집단의 최상단 노드를 더 쉽고 빠르게 찾을 수 있도록 개선하여 시간 초과를 통과했다.

public class Main {

    static int T, F, nodeNum;
    static int[] par = new int[200000]; //집합 부모 노드 배열
    static int[] groupSize = new int[200000]; //집합 사이즈(개수)
    static HashMap<String, Integer> map; //이름 인덱스화
    static StringBuilder answer = new StringBuilder(); //출력
    static String[] names = new String[2];
    static int[] nodes = new int[2];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(bf.readLine());

        for(int i=0;i<T;i++){
            F = Integer.parseInt(bf.readLine());

            Arrays.fill(par, -1);
            Arrays.fill(groupSize, 0);

            nodeNum = 0;
            map = new HashMap<>();

            for(int j=0;j<F;j++){
                StringTokenizer st = new StringTokenizer(bf.readLine());

                names[0] = st.nextToken();
                names[1] = st.nextToken();

                for(int k=0;k<2;k++){//각 이름 입력
                    if(!map.containsKey(names[k])){//기존에 없던 이름이라면
                        map.put(names[k], nodeNum);//인덱스화
                        groupSize[nodeNum] = 1;
                        nodes[k]=nodeNum;//어짜피 최상단 노드는 자기 자신
                        ++nodeNum;
                    }
                    else{//기존에 있던 이름이면
                        nodes[k] = findPar(map.get(names[k]));//이름이 속한 집합 최상단 노드 찾기
                    }
                }

                merge(nodes[0], nodes[1]);//두 집합 merge

                answer.append(groupSize[nodes[1]] + "\n");//그룹사이즈 출력

            }
        }

        System.out.println(answer);
    }

    static int findPar(int node){//집합 최상단 노드 반환
        if(par[node]==-1)
            return node;

        return par[node] = findPar(par[node]);
    }

    static void merge(int node1, int node2) {//두 집합 합치기
        if(node1!=node2){
            par[node1]=node2;
            groupSize[node2] += groupSize[node1];
        }
    }
}

---

결과