[백준-1058] 친구

문제

링크

코드

import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())

graph = []

for _ in range(n) : 
    graph.append(list(input().strip()))

for i in range(n) :
    for j in range(n) :
        # N일 때
        if graph[i][j] == 'N' :
            # 다른 노드끼리 일 때는 INF
            if i != j :
                graph[i][j] = INF
            # 같은 노드 끼리면 0
            else :
                graph[i][j] = 0
        # Y일 때는 1
        else :
            graph[i][j] = 1


# 플로이드-워셜로 문제 풀기
for k in range(n) :
    for a in range(n) :
        for b in range(n) :
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

answer = 0
for i in range(n) :
    tmp = 0
    for j in range(n) :
        # 친구사이의 거리가 2이하일 때만
        if 0 < graph[i][j] <= 2 :
            tmp += 1
    answer = max(answer, tmp)

print(answer)

이 문제를 바보같이 풀었다 !!!
플로이드 워셜을 이용해서 푸는 문제라 쉽게 풀 수 있을 줄 알았는데
예제를 입력하면 다른 값이 나와서 왜 그런지 알 수 없었다...................
그래도 문제는 풀어야 하니까 어쩔 수 없이 다른 분의 풀이를 참고했는데
내가 아주아중 바보같이 생각했다는 걸 알았다 ㅎㅎ..!
백준 질문 검색에 플로이드-워셜로 문제를 풀었다는 어떤 분의 풀이를 볼 때
2보다 작거나 같은 수의 개수를 구하도록 한 부분을 보았다.
그래서 왜 그렇게 문제를 푸는 건지 의문이 들었는데 참고 글에서 궁금증을 해결할 수 있었다!
생각해보니까 2차 배열에 한 명마다 모든 사람까지의 거리가 기록되어 있기 때문이다.
그러므로 0은 아예 도달하지 못했으니까 제외하고,
문제에 서로 친구이거나 한 명을 거쳐서 친구인 경우를 구하라고 했으므로 1, 2의 개수를 구하면 된다.