BOJ - 1058

백준 문제 링크
친구

❓접근법

1. BFS를 사용했다.
2. N과 Y를 받아줄 lst 변수와 친구를 나타낼 graph 변수를 만들어준다.
3. bfs 함수에서 2-친구임을 구별할 count 변수를 만들어 주는데,
   자식 노드(i)에 처음 방문하면 방문 처리해주고,
   부모 노드[v]의 count 값 + 1을 자식 노드에 넣어준다.
   count[i] = count[v] + 1
4. queue를 다 돌게되면 리스트 count가 생기는데,
   적용해야 할 조건은 다음과 같다.

• if i != 0 and i != x: (인덱스가 0도 아니고 시작 노드도 아닐 때)
  • if count[i] == 1 or count[i] == 2:
    ( 두 사람이 친구 / A와 친구이고, B와 친구인 C가 존재할 때)
    • cnt += 1 (2-친구의 수를 1 증가시킨다)

5. 마지막으로 1 ~ N+1 동안 bfs(i)를 실행시켜 answer[i]에 넣어주고,
   최댓값을 찾아주면 끝!

👌🏻코드

from collections import deque

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

answer = [0] * (N+1)

def bfs(x):
    queue = deque()
    queue.append(x)
    
    count = [0] * (N+1)
    cnt = 0
    
    while queue:
        v = queue.popleft()
        
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                count[i] = count[v] + 1
                queue.append(i)
                
    for i in range(len(count)):
        if i != 0 and i != x:
            if count[i] == 1 or count[i] == 2:
                cnt += 1
                
    return cnt

for i in range(1, N+1):
    visited = [False] * (N+1)
    answer[i] = bfs(i)
    
print(max(answer))