[백준] 4195.친구 네트워크

문제 링크

문제 설명

노드끼리 연결되어있는지를 확인하는 문제로 일반적으로 Union-find를 생각해볼 수 있다. 일반적인 Union-find문제와 다르다고 생각한 점은 크게 2가지가 있었다.

• 일반 배열이 아닌 Map을 사용해서 부모의 정보를 저장(Map<String, String>)
• 연결된 노드의 개수를 확인하는 것

Map을 사용한 정점 노드 확인(실패)

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

public class Main {
    static Map<String, String> parent;
    static Map<String, Integer> nameCnt;
    static int cnt;

    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 HashMap<>();
            nameCnt = new HashMap<>();
            for (int i = 0; i < F; i++) {
                st = new StringTokenizer(br.readLine());
                String name1 = st.nextToken();
                String name2 = st.nextToken();

                if(!parent.containsKey(name1)){
                    parent.put(name1, name1);
                }
                if(!parent.containsKey(name2)){
                    parent.put(name2, name2);
                }

                union(name1, name2);
                sb.append(cnt).append("\n");
            }
        }
        System.out.println(sb);
        br.close();
    }
    static String find(String name){
        if(parent.get(name).equals(name)){
            return name;
        }
        return parent.put(name,find(parent.get(name)));
    }

    static void union(String name1, String name2){
        name1 = find(name1);
        name2 = find(name2);

        if(!name1.equals(name2)){
            if(!nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
                parent.put(name2, name1);
                nameCnt.put(name1, 2);
                cnt = 2;
            }else if(nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
                parent.put(name2, name1);
                cnt = nameCnt.get(name1) + 1;
                nameCnt.put(name1, cnt);
            }else if(!nameCnt.containsKey(name1) && nameCnt.containsKey(name2)){
                parent.put(name1, name2);
                cnt = nameCnt.get(name2) + 1;
                nameCnt.put(name2, cnt);
            }else{
                parent.put(name2, name1);
                cnt = nameCnt.get(name1) + nameCnt.get(name2);
                nameCnt.put(name1, cnt);
            }
        }
    }
}

Map을 사용한 부모 정보 저장

for (int i = 0; i < F; i++) {
	st = new StringTokenizer(br.readLine());
	String name1 = st.nextToken();
	String name2 = st.nextToken();
	
	if(!parent.containsKey(name1)){
	    parent.put(name1, name1);
	}
	if(!parent.containsKey(name2)){
	    parent.put(name2, name2);
	}
	...
}

• 처음 등장한 친구의 이름이라면 자기 자신을 부모로 설정하여 Map<String, String> parent 저장한다.

find

static String find(String name){
    if(parent.get(name).equals(name)){
        return name;
    }
    return parent.put(name,find(parent.get(name)));
}

• 재귀 호출을 통해 정점인 노드를 찾기 위한 함수로, return시에 값을 변경해주면서 경로를 압축해준다.

union

static void union(String name1, String name2){
    name1 = find(name1);
    name2 = find(name2);

    if(!name1.equals(name2)){
        if(!nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
            parent.put(name2, name1);
            nameCnt.put(name1, 2);
            cnt = 2;
        }else if(nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
            parent.put(name2, name1);
            cnt = nameCnt.get(name1) + 1;
            nameCnt.put(name1, cnt);
        }else if(!nameCnt.containsKey(name1) && nameCnt.containsKey(name2)){
            parent.put(name1, name2);
            cnt = nameCnt.get(name2) + 1;
            nameCnt.put(name2, cnt);
        }else{
            parent.put(name2, name1);
            cnt = nameCnt.get(name1) + nameCnt.get(name2);
            nameCnt.put(name1, cnt);
        }
    }
}

• Map<String, Integer> nameCnt 는 해당 정점이 몇개의 노드와 연결이 되어있는지 확인하는 것으로, 코드가 많지만 이유는 간단하다. 순서대로 다음과 같다.
  • 두 이름이 모두 처음 등장했을 때 → 왼쪽을 기준으로 부모 값을 설정
  • 두 이름 중 하나가 현재 누군가로부터 정점일 때 → 해당 노드를 기준으로 부모를 설정
  • 둘다 정점인 노드일때 → 왼쪽을 기준으로 두 그룹을 합쳐준다.

결론

• 경로를 압축하는 find 함수에서 put 메소드의 오버헤드라고 판단하여 이를 단순히 부모 값을 리턴하는 코드를 작성했지만 이번에는 메모리 초과가 아닌 틀렸다는 결과를 볼 수 있었다.

정답 코드

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

public class Main {
    static Map<String, Integer> cnt;
    static Map<String, String> parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int num = Integer.parseInt(br.readLine());
            parent = new HashMap<>();
            cnt = new HashMap<>();
            for (int j = 0; j < num; j++) {
                String[] name = br.readLine().split(" ");

                for (int z = 0; z < 2; z++) {
                    if (!parent.containsKey(name[z])) {
                        parent.put(name[z], name[z]);
                        cnt.put(name[z], 1);
                    }
                }
                union(name[0], name[1]);

                bw.write((cnt.get(find(name[1]))) + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();

    }

    static String find(String x){
        if (!x.equals(parent.get(x))) {
            parent.replace(x, find(parent.get(x))); 
        }
        return parent.get(x);
    }
    static void union(String x, String y){
        x = find(x);
        y = find(y);

        if(!x.equals(y)){
            parent.replace(y, x);
            cnt.replace(x, cnt.get(x) + cnt.get(y));
        }
    }
}

find

static String find(String x){
    if (!x.equals(parent.get(x))) {
        parent.replace(x, find(parent.get(x))); 
    }
    return parent.get(x);
}

크게 2가지를 변경했다.

• 자기 자신이 정점이 아닐 때 로 조건문을 수정해서 parent.get(x) 로 리턴하도록 수정
• put이 아닌 replace 를 사용

⭐ put vs replace

이미 존재하는 key의 value값을 업데이트 할때, replace를 사용하는 것이 당연할 수 있겠지만 왜 그런건지 내부 동작을 보면서 살펴봤다.

put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    if (table == null || table.length == 0) resize();
    
    int i = (n - 1) & hash;
    
    if (table[i] != null) {
        ...
    }
    
    table[i] = newNode(hash, key, value, null);

    if (++size > threshold) resize();

    return oldValue;
}

...

final Node<K, V>[] resize() {
      Node<K, V>[] oldTab = this.table;
      int oldCap = oldTab == null ? 0 : oldTab.length;
      int oldThr = this.threshold;
      int newThr = 0;
      int newCap;
		...
}

• resize를 통한 배열 크기 확인
  • 크기가 threshold를 넘었을 때, resize를 호출해서 배열의 크기를 늘리면서 모든 노드를 재배치 하는 과정이 발생
• 중복 키라도 값비교 없이 항상 덮어 씌우기 때문에, 연산 비용이 증가 된다.

replace

public V replace(K key, V value) {
    Node e;
    if ((e = this.getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        this.afterNodeAccess(e);
        return oldValue;
    } else {
        return null;
    }
}

• 반면에, replace 는 탐색을 수행하고 새로운 값으로 변경하기 때문에 메모리 관점에서 훨씬 유리하게 작용하는 것이다.

union

static void union(String x, String y){
    x = find(x);
    y = find(y);

    if(!x.equals(y)){
        parent.replace(y, x);
        cnt.replace(x, cnt.get(x) + cnt.get(y));
    }
}

• 정점을 따로 구분하지 않고 Map<String, Integer> cnt 에 x 값을 기준으로 cnt를 더해서 저장한다.
• 여기서 x 값은 인풋값을 기준으로 왼쪽에 있는 노드를 무조건 부모로 사용한 것인데, 이럴 경우 모두 연결되었을 때 한명의 부모 값을 가지지 못하는 상황이 발생할 수 있다.

1
2
Fred Barney
Betty Fred

{Barney=Fred, Betty=Betty, Fred=Betty}

• 하지만 결국 연결된 노드들의 개수만 파악하면 되기 때문에 이전처럼 관계를 복잡하게 코드로 구현할 필요가 없었다.