[백준/Python] 1058번 - 친구

문제

백준 1058번 - 친구

해결 과정

• 플로이드 워셜 알고리즘 이용
• 흔히 k를 거쳐가는 경로를 구하는 문제는 플로이드 워셜 알고리즘을 떠올려야한다.................

시행착오

• 문제 이해를 잘 ,, 못하겠다 ! 2-친구란?
  • 서로 친구인 경우 = 친구i에서 친구j까지 거리가 1
  • 한 다리 건너서 아는 친구인 경우 = 친구i에서 친구j까지 거리가 2

풀이

import sys
from collections import deque

n = int(sys.stdin.readline())
graph = [list(sys.stdin.readline().strip()) for _ in range(n)]
# 2-친구 사이일 때 1, 아니면 0
f = [[0] * n for _ in range(n)]

for k in range(n):
  for i in range(n):
    for j in range(n):
      if i == j:
        continue
      # 2-친구인 경우
      if graph[i][j] == 'Y' or (graph[i][k] == 'Y' and graph[k][j] =='Y'):
        f[i][j] = 1

res = 0

for row in f:
  res = max(res,sum(row))
print(res)