[코딩테스트] 친구(1058) 최단거리

플로이드 워셜 문제인거는 감이 왔는데 문제에 2- 친구 라는 말이 이해가 안된거는,,다들 그럴꺼같은데 :)

• 단순히 플로이드 워셜 문제에서 i==j 부분에 0을 넣어주고 시작했는데, 계산식이 틀려버려서 실패했었다.

성공.

import sys
input = sys.stdin.readline

n = int(input())

arr = [list(map(str,input().rstrip())) for i in range(n)]
visited = [[0] * (n) for i in range(n)]

for k in range(n):
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			if arr[i][j] == 'Y' or (arr[i][k] == 'Y' and arr[k][j] == 'Y'):
				visited[i][j] = 1

res = 0
for i in visited:
	res = max(res,sum(i))
print(res)

실패.

import sys
input = sys.stdin.readline

n = int(input())

arr = [list(map(str,input().rstrip())) for i in range(n)]
visited = [[0] * (n) for i in range(n)]

 for i in range(n):
 	for j in range(n):
 		if i == j:
 			visited[i][j] = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			if arr[i][j] == 'Y' or (arr[i][k] == 'Y' and arr[k][j] == 'Y'):
				visited[i][j] = 1

res = 0
for i in visited:
	res = max(res,sum(i))
print(res)