[Python] 백준 <1058-친구>

https://www.acmicpc.net/problem/1058

 

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
person = list()

for _ in range(N):
    person.append(input())

max_count = 0
 
# 각 사람의 친구와 2-친구의 수 구하기
for i in range(N) :
    # BFS를 통해 이어진 친구 구하기 (2-친구)
    visited = [0] * N
    # 각 친구와의 거리 (1은 친구, 2부터는 2-친구)
    dist = [-1] * N
    dq = deque()
 
    dq.append(i)
    visited[i] = 1
    # 본인과의 거리는 0 
    dist[i] = 0

    while len(dq) != 0:
        now = dq.popleft()
        for friend in range(N):
            # 현재 now에 해당하는 사람의 친구이고 아직 방문하지 않은 사람이면 i에 해당하는 친구와의 거리 저장
            if person[now][friend] == 'Y' and not visited[friend]:
                dq.append(friend)
                visited[friend] = 1
                dist[friend] = dist[now]+1
    count = 0
    for j in range(N):
        # 본인이 아니고 친구이며 거리가 2이하인 경우 카운트트
        if i != j and dist[j] != -1 and dist[j] <= 2:
            count += 1
    
    # 최대값
    max_count = max(max_count, count)

print(max_count)