[JAVA] 백준 4195 친구 네트워크 - 골드2

 

이전 글(Union-Find 정리 글)

https://fladi.tistory.com/348

[JAVA] Disjoint Set과 Union-Find 알고리즘(백준 1717 집합의 표현)

• 이전에 Union-Find 알고리즘에 대해 공부했다
• 활용문제를 조금 더 풀고싶어 비슷한 문제를 풀어보려고 한다!

 

 

 

 

4195 친구 네트워크 - 골드2

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

4195번: 친구 네트워크

 

 

문제 풀기 전 설계

• 친구관계를 연결하고, 해당 네트워크에 몇 명이 있는지 확인하는 문제다
• 그래프처럼 연결해도 되겠지만, 친구를 몇 명인지 매번 세야한다 -> 시간 초과가 날 확률이 높음
• Union-Find 알고리즘을 사용하여 각 조상 노드에 <현재 네트워크 사람 수>를 저장해두면 빠르게 찾을 수 있을 것 같다
• 사람 이름이 주어지니 Map 자료구조를 사용할 생각이다
• 첫 번째 Map은 부모를 저장할 것이다
  • key에는 내 이름을 저장
  • value에는 내 부모이름을 저장
• 두 번째 Map은 현재 네트워크 사람 수를 저장할 것이다
  • key에는 내 이름을 저장
  • value에는 내 네트워크의 사람 수를 저장 (내가 최고 조상일 때만 사용할 거임. 최고 조상만 갱신)
• 친구관계를 연결하면 Union-Find처럼 조상끼리 연결함 + 네트워크 사람수를 더해 최고조상에 갱신
  • 최고조상에 저장된 네트워크 사람 수를 출력
  • 조상이 같다면 바로 네트워크 사람 수를 출력

 

풀이

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

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tcCnt = Integer.parseInt(br.readLine());
    StringBuffer sb = new StringBuffer();

    for (int t=0; t<tcCnt; t++) {
      int relationCnt = Integer.parseInt(br.readLine());
      parent = new HashMap<>();
      networkCnt = new HashMap<>();

      for (int r=0; r<relationCnt; r++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        String name1 = st.nextToken();
        String name2 = st.nextToken();

        String ancestor1;
        String ancestor2;

        if (parent.get(name1) == null) {
          parent.put(name1, name1);
          networkCnt.put(name1, 1);
          ancestor1 = name1;
        } else {
          ancestor1 = find(name1);
        }

        if (parent.get(name2) == null) {
          parent.put(name2, name2);
          networkCnt.put(name2, 1);
          ancestor2 = name2;
        } else {
          ancestor2 = find(name2);
        }

        if (!ancestor1.equals(ancestor2)) {
          int sum = networkCnt.get(ancestor1) + networkCnt.get(ancestor2);
          networkCnt.put(ancestor1, sum); //name1이 최고 조상
          parent.put(ancestor2, ancestor1);

          sb.append(sum).append("\n");
        } else {
          sb.append(networkCnt.get(ancestor1)).append("\n");
        }
      }
    }

    System.out.print(sb);
  }

  private static String find(String name) {
    if (parent.get(name).equals(name))
      return name;

    String ancestor = find(parent.get(name));
    parent.put(name, ancestor);
    return ancestor;
  }
}

• 내 부모를 저장할 Map -> parent
• 내 네트워크의 사람 수를 저장할 Map -> networkCnt (최고 조상일 때만 사용 및 갱신됨)
• 각 사람의 이름을 받고, 각자의 최고 조상을 찾아 ancestor1, ancestor2에 저장한다
  • Map에 값이 없으면 나를 부모로 넣어주고 내 이름이 ancestor가 된다
  • 최고 조상 찾기는 Union-Find의 find함수를 사용한다
  • find함수는 실행 시 최적화가 일어나도록 하였다 (최고조상으로 갱신)
• ancestor1이 ancestor2와 같다면 이미 친구네트워크에 포함된 사이다 -> 최고 조상의 networkCnt를 출력
• ancestor1과 ancestor2가 같지 않다면
  • ancestor1 네트워크 사람 수를 <내 네트워크 사람 수 + ancestor2 네트워크 사람 수> 로 갱신
  • ancestor2의 부모를 ancestor1로 갱신

 

 

 

 

 

Union-Find만 안다면 어렵지 않게 풀리는 문제였다! 잘 정리해두니 골드2문제도 쉽게 풀려서 기분이 좋다