[백준/파이썬/그래프/BFS] 1058번 친구 코딩테스트 연습풀이

문제 출처: https://www.acmicpc.net/problem/1058

1058번: 친구

 

문제

지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고, B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2-친구의 수를 출력하는 프로그램을 작성하시오.

A와 B가 친구면, B와 A도 친구이고, A와 A는 친구가 아니다.

 

입력

첫째 줄에 사람의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사람이 친구이면 Y, 아니면 N이 주어진다.

 

출력

첫째 줄에 가장 유명한 사람의 2-친구의 수를 출력한다.

 

정답

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

n = int(input())
friends = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    tmp = list(input().rstrip())
    for j in range(n):
        if tmp[j] == 'Y':
            friends[i][j] = 1

def bfs(n, i):
    visited = [0] * n
    visited[i] = 1
    deq = deque([(i, 0)])
    count = 0
    while deq:
        j, cnt = deq.popleft()
        if cnt >= 2:
            continue
            
        for k in range(n):
            if not visited[k] and friends[j][k]:
                count += 1
                visited[k] = 1
                deq.append((k, cnt+1))
                
    return count
        
answer = 0
for i in range(n):
    answer = max(answer, bfs(n, i))
print(answer)

bfs를 통해 문제를 해결하였습니다.