[백준-4195] 친구 네트워크 파이썬, union-find풀이, 파이썬 set을 이용한 풀이

# 문제

 

# 풀이

 문제의 출력을 이해하는데 꽤나 오랜 시간이 걸렸다. "두 사람의 친구 네트워크에 몇 명이 있는지"라는 말 때문이었다. 두사람이면 각각의 출력 결과(2개)가 나와야하는 것이 아닌가라는 의문에 빠졌다. 그러나 친구가 맺어지면 같은 네트워크에 속하게 된다. 그렇기 때문에 하나의 출력이 맞았다.

## 시도했던 풀이

 문제를 보자말자 union-find를 사용해서 풀어야겠다는 생각이 먼저 들었다. 저번에 크루스칼 알고르짐을 풀면서 union-find를 구현했었는데 union-find는 최소신장트리 관리하기 위해서 사용했다. 각 최소신장트리의 root를 비교해보고, 다른 root라면 서로다른 최소신장트리이기때문에, 연결 시켜 줄 수 있다. 

 애석하게도 union-find를 굳이 구현하지 않고 파이썬의 set을 이용해서 푼다면 좋지 않을까라는 생각을 했다. 테스트케이스를 입력받을때 {Fred,Barney}, {Bareny,Betty}, {Betty, Wilma}와 같이 하나의 set으로 입력받고 그 각각의 set은 하나의 최소신장트리로 간주했다. 그리고 set에 isdisjoint를 이용해서 두 트리중 교집합이 존재하는지 확인하고 교집합이 존재한다면 set을 합쳐버리도록 했다. 만약에 set을 합친다면 다시한번 리스트를 검사하도록했다. 테스트케이스를 통과했다. 

그러나 메모리초과...

import sys

def update_networks(networks,network):
  for item in networks:
    if item == network :
      break
    if not network.isdisjoint(item):
      # 교집합이 존재한다면
      network.update(item)
      networks.remove(item)
      networks.append(network)
      update_networks(networks,network)

    else:
      networks.append(network)

def solve2(n):
  for _ in range(n):
    F = int(input())
    networks = []
    for _ in range(F):
      network = set(sys.stdin.readline().strip().split())

      # 맨 처음일때는 그냥 추가
      if len(networks) == 0 :
        networks.append(network)
        print(len(network))
        continue

      update_networks(networks,network)
      print(len(networks[-1]))

if __name__ == '__main__':
    n = int(input())
    solve2(n)

 

 

## 최종 풀이

" Fred,Barney " 를 입력받으면 각각의 사람에 대해서 node를 딕셔너리(dic)를 활용해서 만들어 줬다. 만약 이미 만들어져 있다면 다시 만들 필요는 없다. 그리고 union-find에서 가장 중요한건 해당 node의 root가 자기 자신이라면 그 노드가 root노드가 되는 원리이다.

노드를 만들었다면 node_a <- node_b로 union을 통해 엣지를 만들어줬다. 그리고 일반적인 union-find와 똑같이 코드를 작성했다.

weight를 구하기 위해서는 union시 각 node_b의 최소신장트리의 root가 가진 weight를 node_a의 root에 더해줬다. 

빨간색을 출력해 주면 된다.

 

# 코드

import sys

def find(parent,node):
  # 재귀함수의 종료조건
  # 부모를 찾으면..!
  if parent[node] == node:
    return node
  up = parent[node]
  root = find(parent,up)

  # 다음번에 해당 노드를 방문하여 root를 한번에 찾을 수 있도록
  parent[node] = root

  return root

def union(parent,weight,a,b):
  # 같은 네트워크내에 존재하는지 확인하기 위해서 최소신장트리(root)를 비교해야함
  root_a = find(parent,a)
  root_b = find(parent,b)

  # 같지 않다면 b노드를 a의 root에 연결시켜줌
  if root_a != root_b:
    parent[root_b] = root_a
    # 최소신장트리간 연결될때 해당 트리의 root의 총 weight를 더해줌
    weight[root_a] += weight[root_b]


def solve(n):
  for _ in range(n):
    F = int(input())
    parent = dict()
    weight = dict()

    for _ in range(F):
      node_a,node_b = sys.stdin.readline().strip().split()
      # 노드 초기화
      if node_a not in parent:
        parent[node_a] = node_a
        weight[node_a] = 1
      if node_b not in parent:
        parent[node_b] = node_b
        weight[node_b] = 1

      # a<-b의 엣지 형성
      union(parent,weight,node_a,node_b)
      # 출력은 연결된 놈의 root의 weight를 보여줘야함
      print(weight[find(parent,node_a)])

if __name__ == '__main__':
    n = int(input())
    solve(n)

 

# 마치며

[알고리즘] 크루스칼(Kruskal) 알고리즘 파이썬, 최소신장트리(MST), union-find기법(union-by-rank, path-compr