백준 / 효율적인 해킹 / 1325번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 효율적인 해킹 / 1325번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1325
 
문제 설명
 

---

 
나의 풀이
 

from collections import deque, defaultdict

# 입력 처리
N, M = map(int, input().split())

# 그래프를 인접 리스트로 표현
graph = defaultdict(list)

for _ in range(M):
    A, B = map(int, input().split())
    graph[B].append(A)  # A가 B를 신뢰한다는 것을 B에서 A로 간선으로 표현

def bfs(start):
    visited = [False] * (N + 1)
    q = deque([start])
    visited[start] = True
    count = 1

    while q:
        node = q.popleft()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                q.append(neighbor)
                count += 1
    return count

# 각 컴퓨터를 시작점으로 BFS 수행
max_hacks = 0
result = []

for i in range(1, N + 1):
    hack_count = bfs(i)
    if hack_count > max_hacks:
        max_hacks = hack_count
        result = [i]
    elif hack_count == max_hacks:
        result.append(i)

# 결과 출력
result.sort()
print(" ".join(map(str, result)))

 
bfs를 이용하여 문제를 풀면된다.

---

※ 알아야 할 것

 
특이하게 이 문제는 파이썬으로 제출하면 시간초과가 뜨고 PyPy3로 제출하면 문제가 풀린다.
https://ralp0217.tistory.com/entry/Python3-와-PyPy3-차이

Python3 와 PyPy3 차이