1058번: 친구
지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람
www.acmicpc.net
문제
지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.
A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.
입력
첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.
출력
첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.
코드
n = int(input())
graph = [list(input()) for _ in range(n)]
dist = [[1001]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
dist[i][j] = 0
continue
if graph[i][j] == 'Y':
dist[i][j] = 1
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][j] > dist[i][k]+dist[k][j]:
dist[i][j] = dist[i][k]+dist[k][j]
ans = -1
for i in range(n):
friend = 0
for j in range(n):
if 0 < dist[i][j] <= 2:
friend += 1
if ans < friend:
ans = friend
print(ans)
서로 아는 사이가 거리가 1인 사이라고 했을 때 거리가 2 이하인 사람이 2-친구이다.
모든 사람끼리의 거리를 모두 구하여 2-친구가 가장 많은 사람을 찾았다. 모든 사람끼리의 거리를 구하기 위해서는 모든 정점에서 다른 모든 정점까지의 거리를 구하는 알고리즘인 플로이드-워셜 알고리즘을 사용했다.
'문제풀이 > 최단경로' 카테고리의 다른 글
[Python/파이썬] 백준 20007번 떡 돌리기 (0) | 2024.04.11 |
---|---|
[Python/파이썬] 백준 18223번 민준이와 마산 그리고 건우 (0) | 2024.01.30 |
[Python/파이썬] 백준 4485번 녹색 옷 입은 애가 젤다지? (0) | 2024.01.04 |
[Python/파이썬] 백준 14284번 간선 이어가기 2 (0) | 2023.12.29 |
[Python/파이썬] 백준 1446번 지름길 (0) | 2023.12.15 |