[BOJ] 백준 4195번 : 친구 네트워크 (JAVA)

문제

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

 

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

 

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

 

 

입력

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

 

 

출력

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

 

 

풀이

유니온 파인드를 이용하여 풀 수 있는 문제였습니다. 다만, 연결 관계가 문자열로 주어지고, 중복된 문자열을 접근해야할 수도 있기때문에 Map 자료구조를 사용해야 합니다.

 

그리고 각 노드마다 친구 관계에 해당하는 노드들을 합집합 연산을 해 주어야하는데, 주의할 점이 있습니다.

바로, 단순히 순차적으로 union(a, b)를 취한 후 parent[0] ~ parent[F * 2]까지 parent[a]와 같은 요소는 몇 개인지 계산하는 행위죠.

 

만약, 아래와 같은 예시가 있다고 가정합시다.

 

 

3

Fred Barney

Betty Wilma

Barney Betty

 

 

(0번째 인덱스는 Fred, 1번째 인덱스는 Barney, 2번째 인덱스는 Betty, 3번째 인덱스는 Wilma)

parent[0] = parent[1] = 0이 되면서 2를 출력하고, parent[2] = parent[3] = 2가 되면서 2를 출력하는 것을 알 수 있습니다. 마지막으로, 3번째 줄에서 parent[2] = 0이 되면서 3을 출력하게 됩니다.

 

하지만, 3번째 줄에서는 4가 출력되어야 합니다.

Betty의 루트 노드가 Fred가 되는 순간, 2번째 줄의 Wilma의 루트 노드도 Fred가 되어, 결과적으로 4가 출력되어야 하는 것이죠.

 

이러한 상황을 방지하기 위해서, level이라는 1차원 배열을 정의하여 각 노드마다 층의 개수를 세준 뒤, 합집합 연산을 할 때 합치려는 대상의 층의 개수를 더해 주어야 합니다.

 

위의 예제를 그래프로 표현하여 다시 설명해 보겠습니다.

 

 

<1번째 줄>

 

 

parent[0] = 0, parent[1] = 1에서 합집합 연산을 통해서 parent[0] = parent[1] = 0이 됩니다.

또한, level[0] = level[1] = 1에서 level[0] += level[1]을 취하게 되어 level[0] = 2가 됩니다.

 

 

<2번째 줄>

 

 

<1번째 줄>과 형태가 완전히 같습니다. parent[2] = parent[3] = 2, level[2] = 2로 초기화 됩니다.

 

 

<3번째 줄>

 

 

위와 같이 Betty의 루트노드가 Fred가 되는 동시에 Wilma의 루트노드도 Fred로 바뀌게 됩니다.

따라서 parent[0] = parent[1] = parent[2] = parent[3] = 0이 되는 동시에 level[0] += level[2]을 취하게 되어 level[0] = 2 + 2 = 4가 됩니다.

 

level의 인덱스가 어떻게 변하는지는 아래 소스코드에서 쉽게 이해하실 수 있으니, 지금은 일종의 트리가 합쳐지게 되어 높이의 변화가 일어난 과정을 확실히 알아두시길 바랍니다.

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
    static int[] parent; // 유니온 파인드 루트 노드 배열
    static int[] level; // 각 노드마다 층의 개수
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
 
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int F = Integer.parseInt(br.readLine());
 
            parent = new int[F * 2];
            level = new int[F * 2];
            for (int i = 0; i < F * 2; i++) {
                parent[i] = i;
                level[i] = 1;
            }
 
            int idx = 0;
            Map<String, Integer> map = new HashMap<>();
 
            for (int i = 0; i < F; i++) {
                st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                String b = st.nextToken();
 
                if (!map.containsKey(a)) {
                    map.put(a, idx++);
                }
 
                if (!map.containsKey(b)) {
                    map.put(b, idx++);
                }
 
                sb.append(union(map.get(a), map.get(b)) + "\n");
            }
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
 
        return parent[x] = find(parent[x]);
    }
 
    // 합집합 연산
    public static int union(int x, int y) {
        x = find(x);
        y = find(y);
 
        // 항상 x < y인 값이 들어온다고 가정
        if (x != y) {
            parent[y] = x;
            level[x] += level[y]; // y에 있던 층의 개수를 더해 줌.
 
            // 어차피 y의 부모는 항상 x이므로 level[y]를 접근할 일은 없으므로 꼭 이렇게 초기화해 줄 필요는 없음.
            level[y] = 1;
        }
 
        return level[x];
    }
 
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.