[Python][백준 2660] 회장뽑기

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

2660번: 회장뽑기

---

/*
신경써야 할 부분은 바로 :
1. 입력된 사람들의 친구 관계를 행렬 형태로 저장
2. 최대 회원 수가 50명이므로 시간적 압박은 크지 않다 
	따라서 플로이드 워셜을 사용했다.
3. 각 사람의 가장 먼 사람을 기준으로 잡고 회원들 중 가장 적은 거리를 구한다
4. 그 거리와 그 거리를 가진 회원의 수 를 구하고
5. 회원들의 리스트를 뽑은 후 정렬 후 출력한다.
    
플로이드 워셜만 사용할 줄 알면 그리 어렵지 않다.
*/

---

import sys
input = sys.stdin.readline
 
INF = float('inf')

def floyd_warshall(graph):
    n = len(graph)
    # 최단 경로 행렬 초기화
    dist = [[0 if i == j else graph[i][j] if graph[i][j] != 0 else INF for j in range(n)] for i in range(n)]

    # 동적 프로그래밍을 통한 갱신
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

n = int(input())
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]
while True :
    a,b = map(int, input().split())
    if a == -1 and b == -1 :
        break
    graph[a][a] = 0
    graph[b][b] = 0
    graph[a][b] = 1
    graph[b][a] = 1

# print(graph)

shortest_paths = floyd_warshall(graph)
values = []
result = []

for row in shortest_paths[1:]:
    values.append(max(row[1:]))
    
m = min(values)

for i in range(n):
    if values[i] == m :
        result.append((i+1))

print(m,values.count(m))
print(" ".join(map(str,sorted(result))))

---

풀 때 어려웠던 점 또는 느낀점 :

공익 PS 5일차

플로이드 워셜 문제를 예전에 풀어봤지만

시간이 많이 지나 코드가 잘 기억이 나지 않아 이참에 복습을 했다

몇번 더 풀어봐야 마스터 할 수 있겠지만 난이도가 그리 높진 않아서 다행이다.

이대로 계속 문제를 풀다 보면 플로이드 워셜을 통째로 외울 수 있지 않을까?

---

참고할만한 다른 사람 코드 :

import sys
from collections import deque
input = sys.stdin.readline
q = deque()
N = int(input())
friend = [[] for _ in range(N+1)]
while True:
	a, b = map(int,input().split())
	if a == -1:
		break
	else:
		friend[a].append(b)
		friend[b].append(a)
 
# bfs함수
def bfs(n):
	visited[n] = True
	q.append(n)
	while q:
		x = q.popleft()
		for i in friend[x]:
			if not visited[i]:
				q.append(i)
				dist[i] = dist[x] + 1
				visited[i] = True
 
chairman = []
dab = 51
for i in range(1, N+1):
	dist = [0] * (N+1)
	visited = [False] * (N+1)
	bfs(i)
	m = max(dist)
	if m == dab:
		chairman.append(i)
	elif m < dab:
		chairman = [i]
		dab = m
 
print(dab, len(chairman))
print(*chairman)

# 출처 : https://hbj0209.tistory.com/129

 

위의 코드는 플로이드 워셜을 사용하지 않고 BFS로 구했다.

가중치가 존재하지 않아 가능한 방법이다.