[김태원 알고리즘] 회장뽑기 (플로이드-워셜 알고리즘)

사용 언어: Python3

문제

풀이

내 풀이

N = int(input())
G = [[1000] * N for _ in range(N)]
score = [0] * N # ✅ 각 회장 후보 점수

for i in range(N):
    G[i][i] = 0

while True:
    src, dest = map(int, input().split())
    if (src, dest) == (-1, -1):
        break
    G[src-1][dest-1] = 1
    G[dest-1][src-1] = 1

# 플로이드-워셜
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][k] + G[k][j], G[i][j])

# 회장 점수 계산
for i in range(N):
    score[i] = max(G[i]) # ✅ i의 회장후보 점수(=score[i])는 G[i]의 max 값

# output
mn = min(score)
print(mn, score.count(mn))
for i in range(N):
    if score[i] == mn:
        print(i+1, end=' ')

• 정답!
• 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구 사이이면서 동시에 친구의 친구 사이이면, 이 두 사람은 친구사이라고 본다.
  • “최단거리”로 계산하라는 의미이다.
• 한 회원이 나머지 회원들과의 가까운 정도 중 “최대값”이 그 회원의 “점수”이다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기