[BFS] 백준 #1325 효율적인 해킹 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/1325

 

💡 접근법

BFS/DFS를 사용하여 각 정점에서 이동할 수 있는 정점들의 최대 개수를 구하는 문제이다.

"A가 B를 신뢰하는 경우 B를 해킹하면, A도 해킹할 수 있다." 즉, 방향이 있는 그래프를 만들어 B → A 단방향 그래프를 정의해야 한다.

 

또한 시간복잡도 제한때문에 Python3가 아닌 PyPy3로 제출해야 성공할 수 있다.

 

😎 내 코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[b].append(a)

def BFS(v):
    global cnt, visited
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = True
                queue.append(n)
                cnt += 1

max_value = 0
max_idx = []
for i in range(1, N+1):
    visited = [False] * (N+1)
    cnt = 0
    BFS(i)

    if cnt > max_value:
        max_value = cnt
        max_idx = []
        max_idx.append(i)
    elif cnt == max_value:
        max_idx.append(i)

print(*sorted(max_idx))

 

✅ 정답 확인