[백준] 2610번 회의준비 - 파이썬

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

2610번: 회의준비

풀이

문제풀이에 BFS와 플로이드와샬 알고리즘을 사용해주었다.BFS => 위원회의 개수를 세는데 사용플로이드 와샬 => 최단경로 계산

 

BFS는 우리가 BFS 사이클 문제를 많이 풀어왔다면 문제없이 해결 할  수 있었을 것이다.플로이드 와샬 또한 우리가 양방향 그래프이며 노드간의 직접적인 의사전달이 가능하다면 비용 1을 넣어주었다.

 

문제는 출력문을 뽑아주는것인데 다음단계를 거쳐 출력했다.

 

1, BFS에서 같은 위원회에 속한 노드들을 가져온다.2, 그 노드들 사이에서 한 노드에서 다른 노드까지 걸리는 의사전달시간이 값들을 비교해서 최댓값을 구해준다.3, 다른노드의 최댓값과 비교해서 가장 작은 최댓값을 가진 노드가 이 위원회의 대표자이다.

 

 

example)문제에서 노드 1, 2, 3은 같은 위원회이다.2는 1과 3에게 직접적인 의사전달이 가능하다. 이는 반대방향으로 전달이 가능하다.( 1 -> 2, 3 -> 2 가능)1은 3에게 또는 3은 1에게 직접적인 의사전달이 불가능하다.따라서 1과 3에게 직접적인 전달이 가능한 2가 대표자가 되어야한다.

 

아래 코드에서는 어떻게 진행되는지 보자.

1번 노드에서 같은 위원회에 속한 2, 3에게 의사전달하는데 걸리는 시간 중 최댓값은 3에게 전달하는 시간인 2이다.

(1 -> 2 -> 3)

 

2번 노드에서 같은 위원회에 속한 1, 3에게 의사전달하는데 걸리는 시간 중 최댓값은 1혹은 3에게 전달하는 시간인 1이다.

(2 -> 1, 2 -> 3)

 

3번 노드에서 같은 위원회에 속한 1, 2에게 의사전달하는데 걸리는 시간 중 최댓값은 1에게 전달하는 시간인 2이다.

(3 -> 2 -> 1)

 

따라서 최댓값이 1인 2가 대표자가 되어야 다른 노드에게 가장 효율적으로 의사전달을 할 수 있다.

 

# 2610 회의준비 
# 서로 묶여있는 위원회 찾기 = BFS, 최단경로 구하기 =  플로이드 와샬
import heapq
from collections import deque
import sys
INF = sys.maxsize
input = sys.stdin.readline

def bfs(v):
    queue = deque([v])
    visited[v] = True
    node_li = [v]
    while queue:
        now = queue.popleft()
        for i in range(1, n+1):
            if graph[now][i] != INF and not visited[i]:
                queue.append(i)
                visited[i] = True
                node_li.append(i)
    return node_li

n = int(input())
m = int(input())
groupNum = 0
graph = [[INF]*(n+1) for _ in range(n+1)]
visited = [False] * (n+1)

# 플로이드 와샬
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

for a in range(1, n+1):
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0

for k in range(1, n+1):
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

# BFS를 이용한 위원회의 개수
nums = []
for i in range(1, n+1):
    if visited[i] == False:
        visit_li = bfs(i)
        groupNum += 1
        Maximum = INF
        for k in visit_li:
            # 한 노드에서 최댓값을 찾는 코드.
            Maximum_k = -1
            for j in visit_li:
                if graph[k][j] > Maximum_k:
                    Maximum_k = graph[k][j]
            # 최댓값들 중 가장 작은 최댓값을 구하는 코드.
            if Maximum_k < Maximum:
                Maximum = Maximum_k
                ans = k
        nums.append(ans)
# 오름차순 정렬
nums.sort()
print(groupNum)
for i in nums:
    print(i)

출력결과