4195번(유니온 파인드)

 

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

4195번: 친구 네트워크

이 문제는 유니온 파인드를 사용한 문제인데 조금 문제를 잘못읽고 시작해서 어려움을 겪고 시작했다..

그다음에는 시간 초과로 어려움을 겪고....그 다음은 오답으로 어려움을 겪은 고통 받은 문제이다.

 

문제에서 요구하는 것은 친구관계인 입력이 각 줄에 주어지고, 각줄을 처리하면서 생긴 친구 그룹에 속한 사람의 수를 출력하는 것이다.

예를 들어, 아래와 같은 입력이 주어지면,

Fred Barney
Barney Betty
Betty Wilma

Fred와 Barney가 친구이니까 2명

Barney와 Betty가 친구니까 Fred와 Barney, Betty가 친구니까 3명

Betty와 Wilma가 친구니까 Fred와 Barney, Betty, Wilma가 친구니까 4명이다.

 

다른 예로,

Fred Barney
Betty Wilma
Barney Betty

Fred와 Barney가 친구니까 2명

Betty와 Wilma가 친구니까 2명

Barney와 Betty가 친구니까 Barney와 친구인 Fred, Betty와 친구인 Wilma, 따라서 4명 모두 친구니까 4명이다.

 

따라서 동작은 각각의 노드에 대해 union할 때마다 그룹의 인원을 세어 출력한다.

public int find_root(int x){
        if(x == parent[x]) return x;
        return parent[x]=find_root(parent[x]);
    }
    public void union_root(int x, int y){
        x = find_root(x);
        y = find_root(y);
        if(x!=y){
                parent[x]=y;
                amount[y]+=amount[x];
            }
    }

위의 코드는 유니온 파인드 로직으로 여기서 union할때마다 매번 root노드를 찾을 수 없으니 인원수를 저장하는 amount배열을 추가하였다.

amount배열은 모두 1로 초기화 하여 맨처음 유니온과정을 하기 전에 자기자신만 가지고 있음을 나타내고,

union을 진행 할 때마다 자식노드로 들어가는 노드가 가지고 있는 자식노드의 갯수를 부모노드에 더해준다.

즉, 위의 코드에서 parent[x]=y는 x의 부모 노드를 y로 설정하는 것인데 이때, x가 가지고 있는 친구들을 y에 추가해서 그룹에 속한 총인원을 저장하는 것이다.

예를 들어

A그룹은 1,2,3노드이고, B그룹은 4,5노드일때, 두 그룹을 연결한다면 그룹의 root가 각각 3,5라고 할 때, B에 A를 합친다면 노드 3에 저장된 A그룹의 인원수를 B그룹의 root노드인 5의 값에 더해주어 노드 5에는 2를 5로 갱신한다.(2->5)

그리고 출력 할 때 주의 할 것은 아래의 코드이다.

	int e = g.find_root(map.get(a));
	int f = g.find_root(map.get(b));
    	if(e!=f){
    		g.union_root(e,f);
    	}
	sb.append(g.amount[g.find_root(e)]).append("\n");

나는 이 부분에서 g.amount[e]를 사용했었다. 이 코드의 문제점은 e가 root노드라는 보장이 없다는 것이다.

그래서 44%정도쯤 도달했을 때 계속 오답처리 되었었다.

유니온 파인드를 어느정도 이해했다고 생각했었는데 아직 부족하다는 걸 느꼈다..

더 공부해야겠다.

 

package backjoon.b4195;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class b4195 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<test; i++){
            int relate = Integer.parseInt(br.readLine());//입력받는 이름 수
            HashMap<String, Integer> map = new HashMap<>();//str->int
            int var = 0;//0,1은 대표 2명
            Graph g = new Graph(2*relate);
            int[] parent = new int[2*relate];//그룹의 인원저장
            for(int j=0; j<relate; j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                String a = st.nextToken();
                String b = st.nextToken();
                if(!map.containsKey(a)){
                    map.put(a,var);
                    var++;
                }
                if(!map.containsKey(b)){
                    map.put(b,var);
                    var++;
                }//string->int

                int e = g.find_root(map.get(a));
                int f = g.find_root(map.get(b));
                if(e!=f){
                    g.union_root(e,f);
                }
                sb.append(g.amount[g.find_root(e)]).append("\n");
            }//그룹화
        }
        System.out.println(sb);
    }
}
class Graph{
    int[] amount;
    int[] parent;
    public Graph(int F){
        parent = new int[F+1];
        for(int i=0; i<=F; i++){
            parent[i]=i;
        }
        amount = new int[F+1];
        for(int i=0; i<=F; i++){
            amount[i]=1;
        }
    }
    public int find_root(int x){
        if(x == parent[x]) return x;
        return parent[x]=find_root(parent[x]);
    }
    public void union_root(int x, int y){
        x = find_root(x);
        y = find_root(y);
        if(x!=y){
                parent[x]=y;
                amount[y]+=amount[x];
            }
    }
}