[Baekjoon] 4195번 : 친구 네트워크

1. 문제

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

• 해시, 집합, 그래프 문제

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

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

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

// 입력
첫째 줄에 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며,
이 값은 100,000을 넘지 않는다.
다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진다.
친구 관계는 두 사용자의 아이디로 이루어져 있으며,
알파벳 대문자 또는 소문자로만 이루어진 길이 20 이하의 문자열이다.

// 출력
친구 관계가 생길 때마다,
두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.

// 예제 입력 1
2
3
Fred Barney
Barney Betty
Betty Wilma
3
Fred Barney
Betty Wilma
Barney Betty

// 예제 출력 1
2
3
4
2
2
4

2. 핵심 아이디어

• 해시를 활용한 Union-Find 알고리즘을 이용해 문제를 풀 수 있음
• Python에서는 dictionary를 해시처럼 사용할 수 있음
• Union-Find 알고리즘
  • 원소들의 연결 여부를 확인하는 알고리즘
  • 더 작은 원소를 부모로 삼도록 설정

def find(x) :
  if x == parent[x] :
    return x
  else :
    p = find(parent[x])
    parent[x] = p
    return parent[x]

def union(x, y) :
  x = find(x)
  y = find(y)

  parent[y] = x

parent = []

for i in range(0, 5) :
  parent.append(i)

union(1, 4)
union(2, 4)

for i in range(1, len(parent)) :
  print(find(i), end = ' ')

3. Python 문제풀이

import sys

def find(x) :
  if x == parent[x] :
    return x
  else :
    p = find(parent[x])
    parent[x] = p
    return parent[x]

def union(x, y) :
  x = find(x)
  y = find(y)

  if x != y :
    parent[y] = x
    number[x] += number[y]

test_case = int(sys.stdin.readline())

for _ in range(test_case) :
  parent = dict()
  number = dict()

  f = int(sys.stdin.readline())

  for _ in range(f) :
    x, y = sys.stdin.readline().rstrip().split(' ')

    if x not in parent :
      parent[x] = x
      number[x] = 1
    if y not in parent :
      parent[y] = y
      number[y] = 1

    union(x, y)
    print(number[find(x)])

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
  static int[] parent;
  static int[] number;

  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st;

    int test_case = Integer.parseInt(br.readLine());

    StringBuilder sb = new StringBuilder();
    while (test_case-- > 0) {
      int F = Integer.parseInt(br.readLine());

      parent = new int[F * 2];
      number = new int[F * 2];
      for (int i = 0; i < F * 2; i++) {
        parent[i] = i;
        number[i] = 1;
      }

      int idx = 0;
      Map<String, Integer> map = new HashMap<>();

      for (int i = 0; i < F; i++) {
        st = new StringTokenizer(br.readLine());
        String a = st.nextToken();
        String b = st.nextToken();

        if (!map.containsKey(a)) {
            map.put(a, idx++);
        }
        if (!map.containsKey(b)) {
            map.put(b, idx++);
        }
        sb.append(union(map.get(a), map.get(b)) + "\n");
      }
    }

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }

  public static int find(int x) {
    if (x == parent[x]) {
      return x;
    }
    return parent[x] = find(parent[x]);
  }

  public static int union(int x, int y) {
    x = find(x);
    y = find(y);

    // 항상 x < y인 값이 들어온다고 가정
    if (x != y) {
      parent[y] = x;
      number[x] += number[y]; // y에 있던 층의 개수를 더해 줌.
    }
    return number[x];
  }
}