[Java] 백준 4195번 : 친구 네트워크

1. 문제

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

4195번: 친구 네트워크

 

 

 

2. 풀이과정

 

처음엔 단순하게, 아래 코드처럼 상대방과 상대방과 연결된 노드들에 연결된 노드를 추가시켜주려고 했다. 하지만, 하나의 네크워크의 연결된 정보를 그에 속한 모든 노드들이 중복해서 갖다보니 메모리 초과가 났다..

 

public static void connect(String p1, String p2) {
    Set<String> s1 = personNo.get(p1);
    Set<String> s2 = personNo.get(p2);

    if(s1.contains(p2)) {
        return;
    }

    //상대방과 연결된 것들도 업데이트
    for(String s : s1) {
        if(s.equals(p2)) {
            continue;
        }
        s2.add(s);
    }

    for(String s : s2) {
        if(s.equals(p1)) {
            continue;
        }
        s1.add(s);

        personNo.get(s).addAll(s2);
        personNo.get(s).add(p1);
        personNo.get(s).add(p2);
        personNo.get(s).remove(s);
    }

    //서로 연결
    s1.add(p2);
    s2.add(p1);
}

 

 

그래서 네트워크를 대표하는 한 사람만, 네트워크를 관리해야 했고 Union-Find를 사용했다. 여기서는 두 노드의 부모가 같으면 다시 말해 이미 같은 네트워크에 속해있다면, 합칠 필요가 없다.

 

결론적으로 무조건 다른 네트워크들만 합치기 때문에, 합칠 때 구성 요소의 중복을 확인할 필요없이 각 네트워크에 속한 사람의 수를 더해주면 된다.

 

 

 

결과 코드

 

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

public class Boj4195 {

	static HashMap<String, Integer> network;//자신과 연결된 수
	static HashMap<String, String> parent;//부모
	
	public static String find(String p) {
		if(parent.get(p)==p) {
			return p;
		}
		else { 
			String np = find(parent.get(p));
			parent.put(p, np);//찾으면서 갱신
			return np;
		}
	}
	
	public static int union(String p1, String p2) {
		p1 = find(p1);
		p2 = find(p2);
		if(p1==p2) {//이미 같은 네트워크에 있다면, 있던 값 return (합칠 필요X)
			return network.get(p1);
		}
		
		//연결 안되어 있던 걸 합치므로, 두 네트워크에 속한 사람들의 수를 더하면 된다.
		network.put(p1, network.get(p1)+network.get(p2));
		parent.put(p2, p1);//갱신
		
		return network.get(p1);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int t=0; t<T; t++) {
			int F = Integer.parseInt(br.readLine());
			network = new HashMap<>();
			parent = new HashMap<>();
			for(int i=0; i<F; i++) {
				st = new StringTokenizer(br.readLine());
				String p1 = st.nextToken();
				String p2 = st.nextToken();
                
				//이 사람이 처음 나왔다면, 자기자신을 부모로, 
				//연결된 친구는 1(자기자신)명으로 놓고 출발
				if(!network.containsKey(p1)) {
					parent.put(p1, p1);
					network.put(p1, 1);
				}
				if(!network.containsKey(p2)) {
					parent.put(p2, p2);
					network.put(p2, 1);
				}
				sb.append(union(p1, p2)).append("\n");
			}
		}
		System.out.println(sb.toString());
	}
}