[탐색/BFS] 백준 1325 효율적인 해킹 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1325번: 효율적인 해킹

 

 

2. 문제 풀이

 N개의 컴퓨터가 신뢰하는 관계를 M개의 줄로 A B와 같이 입력받습니다.

 A B는 A가 B를 신뢰한다는 뜻으로, B가 해킹되면 A도 해킹됨을 뜻합니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 보통 그래프 문제에서 A B 입력은 A -> B 를 뜻하지만, 이 문제는 반대입니다. 이를 주의해서 BFS 알고리즘을 사용합니다.

 

 

 

3. 코드

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

# 입력
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[B].append(A)

# bfs
ans = []
for i in range(1, N+1):
    visited = [False]*(N+1)
    queue = deque([i])
    visited[i] = True
    
    cnt = 1
    while queue:
        x = queue.popleft()
        for j in graph[x]:
            if not visited[j]:
                visited[j] = True
                queue.append(j)
                cnt += 1
    ans.append(cnt)

max_cnt = max(ans)
for i in range(N):
    if ans[i] == max_cnt:
        print(i+1, end=" ")