Part7.13_동적프로그래밍(DynamicProgramming)_회장뽑기(플로이드-워샬 응용)

문제

!

입력

입력의 첫째 줄에는 회원의 수가 있다.
단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데,
이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 회원의 수만큼 번호가 붙어있다.
마지막 줄에는 -1이 두 개 들어있다

출력

첫째 줄은 회장 후보의 점수와 회장후보 수를 출력하고 두 번째 줄은 회장 후보를 모두 출력
한다.

정답 풀이

• 플로이드 알고리즘

1. 배열 초기화(처음 모두 100으로)
   

2. 간선 초기화(직행 노드 & 대각선 0)
   

3. 플로이드 워샬 알고리즘
   
   

4. res 기록
   

정답 코드

import sys
sys.stdin = open ("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    #n 은 정점번호, m은 간선의 개수
    n = int(input())

    dis=[[100]*(n+1) for _ in range(n+1)]

    for i in range(1,n+1):
        dis[i][i] = 0 #대각선 0으로 초기화

    while True:
        a, b = map(int,input().split())
        if a==-1 and b == -1:
            break
        dis[a][b] = 1
        dis[b][a] = 1

    for k in range(1,n+1): # 플로이드 워샬 알고리즘
        for i in range(1, n+1):
            for j in range(1, n+1):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]) 

    res=[0]*(n+1)
    score = 100
    for i in range(1, n+1): # 최댓값 max에 저장
        for j in range(1,n+1):
            res[i]= max(res[i], dis[i][j]) #i번 회원의 가까운 정도 최댓값 기록된다.
        score = min(score, res[i])
    out=[]
    for i in range(1, n+1):
        if res[i]==score:
            out.append(i)
    print("%d %d" %(score, len(out)))
    for x in out:
        print(x)

코멘트