[Baekjoon] Shortest Path - 1058 친구

문제

1058번: 친구

 

풀이

플루이드 워셜(floyd warshall)로 문제를 풀 수 있다.

2-친구가 되기 위한 조건이 2가지가 있다.

 

1) A=B 친구인 경우

2) A=C, B=C 친구인 경우

 

1, 2번 조건을 만족하기 위해 거치는 노드를 제한해야한다.

길이가 1이므로 최대 길이가 2이하일 때만 2-친구가 가능하다.

 

아래 상황 1에서는 A를 기준으로 거리가 2이하인 B, C가 2-친구이다.

상황 1) A를 기준으로 친구 관계도를 그린 경우

아래 상황 2에서는 B를 기준으로 거리가 2이하인, A, C, D가 2-친구이다.

상황 2) B를 기준으로 친구 관계도를 그린 경우

 

2-친구가 가장 많은 사람의 2-친구의 수를 출력해야하므로, 특정 인원의 2-친구의 수 중 가장 큰 값을 찾으면 된다.

 

import sys

INF = 1e9

n = int(sys.stdin.readline().rstrip())
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

for i in range(1, n + 1):
    text = sys.stdin.readline().rstrip()
    for j in range(1, n + 1):
        if text[j - 1] == 'Y':
            # 친구 관계 (양방향)
            graph[i][j] = 1
            graph[j][i] = 1

for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            # 2-친구가 되기 위한 조건
            if graph[i][k] + graph[k][j] <= 2:
                graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])


# 가장 많은 2-친구의 수
max_result = 0

for i in range(1, n + 1):
    max_result = max(max_result, len(list(filter(lambda x: x != 0 and x != INF, graph[i]))))

print(max_result)

 

채점 결과