[백준2610&파이썬] 플로이드-와샬과 유니온파인드를 함께 이용해보자.

# 문제

백준 2610 회의준비 파이썬 풀이

2610번: 회의준비

# 코드

'''
  - 플로이드-와샬을 이용해서 다른 노드까지의 방문의 합이 최소인 노드를 대표로노드로 선정한다
    - 근데 같은 집단(위원회)인건 어떻게 구별해야하나?
    - 보통 집단을 찾는건 BFS를 활용하기는 하는데.. OR UNION - FIND
    - 일단 못가는 곳은 INF로 표현 되긴 함
    - 유니온 파인드로 구분하는 전처리 과정을 거치자
      https://eun-jeong.tistory.com/15
'''

import sys
from collections import defaultdict

N = int(sys.stdin.readline()) # 참석 하는 사람의 수
M = int(sys.stdin.readline()) # 서로 알고 있는 사람

distance = [[float('inf')] * (N+1) for _ in range(N+1)]

# union-find로 집합여부를 먼저 판단하자
parent = [i for i in range(N+1)]
rank = [1 for i in range(N+1)]

def find(node) :
  if parent[node] == node :
    return node
  parent[node] = find(parent[node])
  return parent[node]

def union(nodeA, nodeB) :
  a = find(nodeA)
  b = find(nodeB)

  # 항상 높이가 더 낮은 트리를 높이가 더 높은 트리 밑에 넣는다.
  if rank[a] < rank[b] :
    parent[a] = b
  else :
    parent[b] = a
    if rank[a] == rank[b] : # Rank가 같다면, b를 a에 붙였기 때문에 a의 랭크를 1 올려줘야함 ( 루트 )
      rank[a] += 1



for _ in range(M) :
  a,b = map(int,sys.stdin.readline().split())
  # 양방향 관계
  distance[a][b] = 1
  distance[b][a] = 1
  union(a,b) # 유니온 파인드 수행



for i in range(N+1) :
  distance[i][i] = 0 # 시작 노드 초기화


for pivot in range(1, N+1) :
  for start in range(1, N+1) :
    for end in range(1, N+1) :
      distance[start][end] = min(distance[start][pivot] + distance[pivot][end], distance[start][end])





result = defaultdict(lambda : (float('inf'), -1)) # 초기값을 inf로 하기 위해서
for index,item in enumerate(parent[1:]) :
  index += 1
  item = find(item) # parent에서 꺼낸 노드의 값이 항상 부모는 아니기 때문에 부모 노드를 찾아야한다.

  # 최대값 찾기
  # 찾은 최대값과 현재 캐싱된 값 비교
  # 찾은 최대값이 더 작다면 업데이트

  mmax = -1
  for i in distance[index][1:] :
    if i == float('inf') :
      continue
    if mmax < i :
      mmax = i # 최대값 찾기

  if mmax < result[item][0] :
    result[item] = (mmax, index)


# print(parent)
# print(result)
# for i in range(1,N+1) :
#   print(*distance[i][1:])
# print()

print(len(result))
for item in sorted(list(result.values()), key = lambda x : x[1] ) :
  print(item[1])

# 풀이

## 주의사항

아래와 같은 사항들을 생각하지 못해서 다 풀어놓고 정답까지 많은 시간을 소비해버렸다.

• 모든 참석자들의 의사전달 시간의 총합중의 최소값을 구하는 것이 아니다. 모든 참석자들의 의사전달시간중 최대값을 구하고 그 최대값이 가장 작은 것을 구해야한다.
• UNION-FIND를 사용했으면, 그로 인해 얻어낸 PARENT 배열을 그대로 사용한다면 그건 그 노드의 부모노드가 아니다. PARENT안에 들어있는 값을 통해 find를 해야지 부모의 노드가 나온다. ( 즉 자기가 속한 집단 )

## 접근방법

• 이 문제를 해결하기 위해서 아래와 같이 두가지 방법을 어떻게 수행해야할지 고민했다.
  • 각 노드에서 시작하는 의사전달의 최대값을 어떻게 구해낼 것인가? 이것은 모든 노드로부터 시작하는 것을 찾아봐야한다.
  • 어떤 집단(위원회)에 속하는지 그룹핑을 어떻게 할 것인가?

 

• 첫번째는, 플로이드-워셜을 사용해서 모든노드에서 시작하여 모든 노드까지의 도착하는 거리들을 찾아내고, 해당 거리중 최대값들을 찾아내는것으로 어렵지 않게 해결했다.
• 두번째는, 각 집단을 어떻게 그룹핑 할 것인가에 대한 고민인데, 이걸 플로이드-와샬을 통해서 한번해 해보려고 했는데 좋은 방법이 생각나지 않았고, BFS나 Union-find로 해결하고자했다. BFS보단 Union-find가 빠를거 같았기 때문에 해당 풀이 방법을 선택했다.
• Union-Find는 많이 사용해봤지만, rank를 이용한 최적화는 처음 사용해봤다. 보통 root를 find시에 초기화 해주는거 까지 해줬었다. rank를 이용할때는, a,b의 rank를 비교하고 rank가 큰 쪽에 작은거를 붙여주는 식으로 활용한다. 그렇다면 rank의 길이는 큰쪽의 상태가 되기 때문에 따로 변화되지 않는다. 
• 만일 Rank가 같다면 rank의 크기를 1올려줘야 한다. 이 원리는 간단하다. 밑으로 들어가기 때문이다.

 

# 참고

[알고리즘] 유니온 파인드 : Union-Find (Disjoint Set)