📙[Algo] 24.04.21 알고리즘

알고리즘 문제) BOJ 4195. 친구 네트워크

4195번: 친구 네트워크

문제 요약

• 친구 관계가 주어 질때마다, 두 사람의 친구 네트워크에 몇 명이 있는지 구하기
  • 친구 네트워크 → 같은 연결요소

시간 제한

• 3초

입력

• 테스트 케이스 개수
• 각 테스트 케이스별로
  • 친구 관계수 F
  • F개의 줄에 친구 관계가 주어짐(아이디)
    • 알파벳 대문자 또는 소문자(길이 20이하 문자열)

출력

• 친구 관계가 생길 때마다, 두 사람의 친구 네트워크에 몇 명 있는지 출력

접근법

• 일단 입력이 문자열로 주어진다. → Map에 <이름, 노드번호>로 기록해둘 것
  • 만약 입력이 
    Fred Barney
    Barney Betty
    Betty Wilma
    위 처럼 주어진다면, map에는 {”Fred” : 1, “Barney” : 2, “Betty” : 3, “Wilma” : 4}가 기록된다.
    즉, 이름이 키값이 된다(입력을 이름으로 받고, 나중에 union할 때 노드 번호를 넘겨줘야 하므로 이름을 키값으로 설정했다).
    map에 담을 때마다 map.containsKey(입력값)이 존재하는지 체크 하자!
• 또한, union 함수를 만들어서 두 친구를 같은 연결요소로 합쳐야 하므로
  • union(map.get(입력1), map.get(입력2))를 통해 연결요소를 합쳐준다.
• 그 다음 각 입력마다 속해 있는 연결요소의 크기를 반환한다.
  • parent 배열에서 find(입력값)의 값과 같은 만큼 개수를 카운트 해준다.
    • 여기서, parent배열은 친구 수가 몇 명인지 주어지지 않으므로, 최대 가능한 친구 관계수 10만*2+10만큼 크기를 잡자!
• 시간초과 문제 해결
  • 그냥 매 케이스마다 같은 루트 노드를 갖고있는 개수를 카운트 한다면 시간초과가 뜬다. (최악의 경우, 10만 * 10만이 되므로)
  • 그래서 아예 루트 노드별 연결요소 크기를 담을 sizeGraph 배열을 만들고, union할 때마다 size를 더해준다.
    parent[b] = a;
    sizeGraph[a] += sizeGraph[b];

코드

import java.io.*;
import java.util.*;

public class Main {
    static int F;
    static int[] parent = new int[200010];
    static int[] sizeGraph = new int[200010];

    static int find(int x) {
        if (parent[x] == x) return x;

        parent[x] = find(parent[x]);
        return parent[x];
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
        sizeGraph[a] += sizeGraph[b];
    }

    public static void main(String[] args) throws 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) {
            F = Integer.parseInt(br.readLine());

            // 부모 배열 초기화
            for (int i = 0; i < 20010; i++) {
                parent[i] = i;
            }

            // 연결요소 크기담을 배열 초기화(최소 1개는 갖고 있으니 1로 초기화)
            Arrays.fill(sizeGraph, 1);

            Map<String, Integer> map = new TreeMap<>();

            String f1, f2;
            int nodeNum = 1, v1, v2;
            for (int i = 0; i < F; i++) {
                st = new StringTokenizer(br.readLine());
                f1 = st.nextToken();
                f2 = st.nextToken();

                if (!map.containsKey(f1)) map.put(f1, nodeNum++);
                if (!map.containsKey(f2)) map.put(f2, nodeNum++);

                v1 = map.get(f1);
                v2 = map.get(f2);

                if (find(v1) == find(v2)) {
                    // 이미 같은 연결요소에 속한 경우
                    sb.append(sizeGraph[find(v1)] + "\n"); // 기존에 기록된 연결 요소 크기를 반환
                    continue;
                }

                // 같은 연결요소로 합쳐준다.
                union(v1, v2);

                sb.append(sizeGraph[find(v1)] + "\n");
            }
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}