[백준/BOJ] 1058 - 친구

1058 - 친구

📌 문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

📋 코드

N = int(input())
graph = [list(input()) for _ in range(N)]
visited = [[0 for _ in range(N)] for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            if graph[i][j] == 'Y' or (graph[i][k] == 'Y' and graph[k][j] == 'Y'):
                visited[i][j] = 1

result = 0
for visit in visited:
    result = max(result, sum(visit))
print(result)

💡 한마디

처음엔 뭔말인가 싶었는데 찬찬히 읽어보니 플로이드-워셜로 바로 풀 수 있는 문제였다. 반복문 안에 있는 if문에서 i 와 j 가 직접적인 친구거나 서로 아는 사람이 있어 친구가 되는 경우 visited 리스트를 1로 초기화 시켰고, 각 행의 합이 최소인 값을 골랐다.

1058번: 친구