백준 1058 친구 / python

문제 : 1058

풀이 point

5567문제와 유사하다.

2 친구 수를 구하기 위해서는 depth가 2번일 때까지만 탐색하면 된다.

풀이 방법

입력 데이터를 통해 연결리스트를 만든 후 각 사람마다 2친구 수를 구한다. 예를들어 1번 사람의 2친구 수를 구할 때는 1과 연결된 친구(2 친구)만 탐색하기 위해

if node == num:
   Q.append(n)

현재 탐색하는 노드가 1인지 확인 후 맞다면 그때만 Q에 1과 연결된 친구(2 친구)를 집어 넣어 탐색을 한다. 만약 아니라면 큐에 들어가지 않기 때문에 자동으로 탐색이 되지 않는다.
(오로지 2 친구만 탐색 가능)

풀이 코드

#본인 친구 갯수 + depth가 2 이내인 친구들 개수 중 가장 많은 사람
from collections import deque

def bfs(num):
  cnt = 0
  Q = deque()
  Q.append(num)
  visit = [False]*(N+1)
  visit[num] = True
  while Q:
    node = Q.popleft()

    for n in graph[node]:
      if not visit[n]:
        visit[n] = True
        cnt += 1
        if node == num:
          Q.append(n)
  return cnt

N = int(input())
count = [0]*(N+1)

graph = [[] for _ in range(N+1)]
for i in range(1, N+1):
  row = input()
  for j in range(N):
    if row[j] == 'Y':
      graph[i].append(j+1)

for i in range(1, N+1):
  count[i] = bfs(i)

print(max(count))