[백준] 4195 친구 네트워크

1. 문제

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

4195번: 친구 네트워크

2. 접근방법

union find의 기본형 문제

숫자 대신 String으로 주어지는 것만 다르다.

 

Map으로 부모관계를 나타내주고

다른 Map으로 가장 최상위 부모에게만 현재 네트워크의 친구 수를 저장한다.

union 되는 과정에서 두 네트워크의 친구수만 더해서 저장해주면 된다.

 

그리고 find할 때 모든 노드의 부모를 최상위 부모로 바꾸는 작업을 했는데

안하면 시간초과 날지도?

 

또 이미 같은 네트워크인 친구 둘이 나왔을 때의 예외처리도 해주어야 한다.

3. 자바 코드

package backjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class P4195친구네트워크 {


    static Map<String, String> parentMap;
    static Map<String, Integer> networkMap;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            parentMap = new HashMap<>();
            networkMap = new HashMap<>();
            int F = Integer.parseInt(br.readLine());
            while (F-- > 0) {
                st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                String b = st.nextToken();
                System.out.println(union(a,b));
            }
        }
    }

    static int union(String a, String b) {
        String aBoss = find(a);
        String bBoss = find(b);

        int aNetwork = networkMap.getOrDefault(aBoss, 1);
        int bNetwork = networkMap.getOrDefault(bBoss, 1);
        if(aBoss.equals(bBoss))
            return aNetwork;
        parentMap.put(bBoss, aBoss);
        networkMap.put(aBoss, aNetwork + bNetwork);
        return aNetwork + bNetwork;
    }

    static String find(String a) {
        String parent = parentMap.getOrDefault(a, a);
        if (parent.equals(a))
            return a;
        else {
            String boss = find(parent);
            parentMap.put(a, boss);
            return boss;
        }
    }
}

4. 마치며

책정된 난이도에 비해 평이했다.