[백준] 4195 친구 네트워크 - 유니온파인드(Union Find) + 해쉬맵(HashMap) JAVA

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

4195번: 친구 네트워크

코드설명

유니온 파인드에 HashMap을 추가로 사용하여 진행합니다. 

 

 

문제 로직입니다.

이 문제같은경우, 일반적으로 친구들이 Index 형태로 주어지지않고, 문자열 형태의 이름으로 주어졌습니다.

우리는 이 친구들의 이름을 HashMap을 활용하여 이름을 지어주어서 일종의 Index를 지은뒤 unionFind하는 알고리즘에 사용할 것입니다. 

HashMap은 친구들의 Indexing 을 하기 위한 도구입니다.

 

문제에 주어지듯 F개의 줄에 친구관계가 주어집니다.

이때 친구는 2개씩 F개의 줄이 주어졌을때, 모두 이름이 다를경우 2*F의 친구가 있으므로 F*2의 사이즈로 선언합니다.

parent = new int[F*2];
friendCount = new int[F*2];
 
for(int i=0;i<F*2; i++) {
    parent[i] = i; //본인의 index로 초기화시킵니다. 본인의 집합은 본인을 가리킵니다.
    friendCount[i] = 1; //처음 친구수는 1명 본인입니다.
}

• parent[i] = i 로 선언
• friendCount는 항상 처음에는 친구수가 본인 1명

만약에 Fred Barney가 주어졌다고 가정합니다.

맨 처음에 말했듯이 HAshMap을 활용하여 친구들의 번호를 Indexing합니다.

<Fred : 0 >

<Barney : 1>

이렇게 HashMap에 데이터가 들어갑니다.

int friendIdx = 0;
HashMap<String, Integer> hashmap = new HashMap<>(); //<String : 이름, index : (노드번호) >
for(int i=0;i<F;i++) {
    st = new StringTokenizer(br.readLine());
    String friendA = st.nextToken();
    String friendB = st.nextToken();
 
    if(hashmap.containsKey(friendA) == false) { //만약 처음 만난 친구라면, 즉 친구관계에 한번도 union된적 없을경우 index를 저장하기 위한 처리입니다.
        hashmap.put(friendA, friendIdx++);
    }
    if(hashmap.containsKey(friendB) == false) { //만약 처음 만난 친구라면, 즉 친구관계에 한번도 union된적 없을경우 index를 저장하기 위한 처리입니다.
        hashmap.put(friendB, friendIdx++);
    }
    sb.append(unionParent(hashmap.get(friendA), hashmap.get(friendB))).append("\n");
}

 

그리고 unionParent( 0, 1 )을 통해서 친구가 총 몇명인지 구합니다.

아래에서 a == b 일경우 같은 친구 그룹에 속하는 것을 의미합니다. 이미 구해졌다는 의미입니다.

그러므로 friendCount[a]를 return 하면됩니다.

만약 a != b 일경우에는, 기본적으로 a < b, 즉 인덱스가 작을 수록 부모로 선언하도록 우선순위를 둡니다.

parent[b] = a; ( b가 a를 가리키도록 수정합니다.)

또한 우리는 ( a가 지금까지 총 몇명의 친구를 구했는지 알고싶기에 )

friendCount[a] += friendCount[b] 를 통해서 a 그룹에 b그룹의 친구수를  더해줍니다.

그리고 return friendCount[a]를 내보냅니다. 

a >= b 일경우 위의 로직과 같습니다.

public static int unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
 
    if( a != b) {
        if(a < b) {
            parent[b] = a;
            friendCount[a] += friendCount[b]; //a번쨰 Index에 친구수의 값을 함께 합쳐줘야합니다.
            return friendCount[a];
        }
        else if( a >= b){ 
            parent[a] = b;
            friendCount[b] += friendCount[a];
            return friendCount[b];
        }
    }
    return friendCount[a];
}

 

틀렸었던 부분은, 아래의 코드입니다.

a와 b가 같은경우에 또한 else를 통해서 parent[a] = b, friendCount[b] += friendCount[a]; return friendCount[b] 로직이 실행되었습니다. 

만약 a == b 인 조건이라면, 더하기 연산을 진행하지 않고 바로 friendCount[a] 를 반환해야합니다.

    public static int unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	
//		a와 b가 같은경우, 더하기 로직을 진행하면 안됩니다.
//    	if(a < b) {
//    		parent[b] = a;
//    		friendCount[a] += friendCount[b];
//    		return friendCount[a];
//    	}
//    	else {
//    		parent[a] = b;
//    		friendCount[b] += friendCount[a];
//    		return friendCount[b];
//    	}
    	
		if( a != b) {
			if(a < b) {
				parent[b] = a;
				friendCount[a] += friendCount[b]; //a번쨰 Index에 친구수의 값을 함께 합쳐줘야합니다.
				return friendCount[a];
			}
			else if( a >= b){ //사실 로직상 idx는 계속해서 증가하는 형식이므로 이 경우는 없지만 추가합니다. 
				parent[a] = b;
				friendCount[b] += friendCount[a];
				return friendCount[b];
			}
		}
		return friendCount[a];
    	
    }

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int T, F;
	public static int[] parent; //유니온 집합셋
	public static int[] friendCount; //각 인덱스별 친구의 수 
	public static StringBuilder sb = new StringBuilder();
	public static int answer = 0;
	
	public static int findParent(int x) {
		if( x == parent[x]) return x;
		else return parent[x] = findParent(parent[x]);
	}
	
	public static int unionParent(int a, int b) {
		a = findParent(a);
		b = findParent(b);
		
		if( a != b) {
			if(a < b) {
				parent[b] = a;
				friendCount[a] += friendCount[b]; //a번쨰 Index에 친구수의 값을 함께 합쳐줘야합니다.
				return friendCount[a];
			}
			else if( a >= b){ 
				parent[a] = b;
				friendCount[b] += friendCount[a];
				return friendCount[b];
			}
		}
		return friendCount[a];
		
//		if( a < b ) parent[b] = a;
//		else parent[a] = b;
	}
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	T = Integer.parseInt(st.nextToken());
    	
    	for(int t=0;t<T;t++) {
    		st = new StringTokenizer(br.readLine());
    		F = Integer.parseInt(st.nextToken());
    		parent = new int[F*2];
    		friendCount = new int[F*2];
 
    		for(int i=0;i<F*2; i++) {
    			parent[i] = i; //본인의 index로 초기화시킵니다. 본인의 집합은 본인을 가리킵니다.
    			friendCount[i] = 1; //처음 친구수는 1명 본인입니다.
    		}
    		
    		int friendIdx = 0;
    		HashMap<String, Integer> hashmap = new HashMap<>(); //<String : 이름, index : (노드번호) >
    		for(int i=0;i<F;i++) {
    			st = new StringTokenizer(br.readLine());
    			String friendA = st.nextToken();
    			String friendB = st.nextToken();
    			
    			if(hashmap.containsKey(friendA) == false) { //만약 처음 만난 친구라면, 즉 친구관계에 한번도 union된적 없을경우 index를 저장하기 위한 처리입니다.
    				hashmap.put(friendA, friendIdx++);
    			}
    			if(hashmap.containsKey(friendB) == false) { //만약 처음 만난 친구라면, 즉 친구관계에 한번도 union된적 없을경우 index를 저장하기 위한 처리입니다.
    				hashmap.put(friendB, friendIdx++);
    			}
    			sb.append(unionParent(hashmap.get(friendA), hashmap.get(friendB))).append("\n");
    		}
    		
    	}
    	System.out.println(sb.toString());
    	
    }
    
    
}