[baekjoon] 백준 1058번(파이썬): 친구

문제

1058번: 친구

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 사람마다 친구와의 관계를 bfs로 탐색한다.

- 친구와의 관계가 2 미만인 경우만을 생각한다.

- 각 사람마다 2-친구의 수를 구했다면 거기서 제일 유명한 사람을 출력한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs(v):
    visited = [False] * n
    queue = deque([[v, 0]]) # 사람의 번호와 친구와의 관계
    visited[v] = True
    cnt = 0
    while queue:

        a, b = queue.popleft()

        # 친구와의 관계가 2이상이면 생각하지 않는다.
        if b >= 2:
            continue

        # 반복문을 통해 탐색하지 않은 사람이고 그 사람이 친구가 있는지 확인
        for i in range(n):
            if not visited[i] and graph[a][i] == "Y":
                cnt += 1
                visited[i] = True
                queue.append([i, b + 1])

    return cnt


n = int(sys.stdin.readline())
graph = [list(map(str, sys.stdin.readline().strip())) for _ in range(n)]

res = 0
# 각 사람마다 친구의 2-친구의 수를 구하고 제일 유명한 사람을 출력한다.
for i in range(n):
    res = max(res, bfs(i))

print(res)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법