[BaekJoon] 4195번 친구 네트워크 (Java) 문제 풀이 [Gold 2]

문제

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

4195번: 친구 네트워크

 

어떻게 풀 것인가?

문제를 읽어보자.

 

", 두 사람의 친구 네트워크에 몇 명이 있는지 구하는" 이라는 어절을 읽었을 때, 집합에 대한 개념과 이를 이용한 유니온-파인드 알고리즘을 떠올려서 문제를 풀었다.

 

하지만 시간초과가 발생했다.

 

왜 일까? 단순 유니온 - 파인드 알고리즘만을 이용한다면, 공통된 친구를 찾는 부분에서 시간초과가 발생했다.

 

그래서 HashMap을 이용하여 시간복잡도를 줄였다. HashMap에서 Data를 Search하는 것은 시간복잡도가 O(1)이기 때문이다.

 

풀면서 놓쳤던점

연결 관계가 문자열로 주어지고, 중복된 문자열을 접근해야할 수도 있기때문에 Map 자료구조를 사용을 놓쳤다.

 

이 문제를 통해 얻어갈 것

유니온 - 파인드 알고리즘과 Map을 이용한 풀이 방법

 

내 코드 

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

// 백준알고리즘 4195번 친구 네트워크
public class Main {
    static int[] parent;
    static int[] level;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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 first = st.nextToken();
                String second = st.nextToken();

                if (!map.containsKey(first)) {
                    map.put(first, idx++);
                }

                if (!map.containsKey(second)) {
                    map.put(second, idx++);
                }

                sb.append(union(map.get(first), map.get(second))).append("\n");
            }
        }
        System.out.println(sb);
        br.close();
    }

    public static int find(int num) {
        if (num == parent[num]) {
            return num;
        }

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

    // 합집합 연산
    public static int union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            parent[y] = x;
            level[x] += level[y];
            level[y] = 1;
        }

        return level[x];
    }
}

 

참고

https://superohinsung.tistory.com/130

[Algorithm] 유니온 파인드(Union-Find) 알고리즘