[BOJ] 4195 친구 네트워크 - JAVA

1. 문제

4195번: 친구 네트워크

민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.

어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.

---

2. 풀이

• map에 해당 key를 가진 값이 없을 때의 초기화를 위해 putIfAbsent 메서드를 사용했다.
• putIfAbsent의 함수는 다음과 같이 동작한다. 

default V putIfAbsent(K key, V value) {
    V v = get(key);
    if (v == null) {
        v = put(key, value);
    }
    return v;
}

 

메인

• 이제까지 풀던 union find 문제를 map으로 바꾸면 된다.
• 연결정보를 저장하는 network, 친구가 몇 명 이어져있는지 저장하는 depth 총 두 개의 map을 사용했다.
• 친구 둘을 입력받은 후 처음 등장하는 친구라면 두 가지의 map에 기본값을 넣었다. 
• 친구 둘을 합친 후 둘 사이에 몇 명이 있는지를 출력한다.

static Map<String,String> network;
static Map<String, Integer> depth;
public static void main(String[] args) throws IOException {
   StringBuilder sb = new StringBuilder();
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;
   int T = Integer.parseInt(in.readLine());
   while(T-->0){
      int F = Integer.parseInt(in.readLine());
      network = new HashMap<>();
      depth = new HashMap<>();
      for(int i=0;i<F;i++){
         st = new StringTokenizer(in.readLine());
         String a = st.nextToken();
         String b = st.nextToken();
         network.putIfAbsent(a, a);
         network.putIfAbsent(b, b);
         depth.putIfAbsent(a,1);
         depth.putIfAbsent(b,1);
         sb.append(union(a,b)).append("\n");
      }
   }
   System.out.print(sb);
}

 

Union

• 루트값을 찾아서 루트가 같다면 그 루트의 depth를 반환한다.
• 루트가 다르다면 어떤 depth가 더 작은지 찾고 작은 값의 루트를 큰 값으로 교체한다.
• depth도 변경해야하는데, 큰 값의 depth를 두 depth의 합으로 변경한다.
• 마지막으로 두 depth의 합을 반환한다.

private static int union(String a, String b) {
   String pa = find(a);
   String pb = find(b);
   if(pa.equals(pb)) return depth.get(pa);

   int da = depth.get(pa);
   int db = depth.get(pb);

   if(da>=db){
      network.replace(pb,pa);
      depth.replace(pa,da+db);
   }else{
      network.replace(pa,pb);
      depth.replace(pb,da+db);
   }

   return da+db;
}

 

Find

• 이전에는 int[]를 사용해서 return set[x] = find(set[x])가 가능했지만, map의 replace 함수는 변경 전 이전 값을 반환하기 때문에 그렇게 하면 안된다. 따라서 replace를 진행한 뒤에 get(x)를 한다.

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

---

3. 결과

map의 replace함수 작동을 착각해서 한 번 틀렸다.