[백준/알고리즘] #1325: 효율적인 해킹 [파이썬(python)/그래프/DFS/BFS]

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

1325번: 효율적인 해킹

시간제한이 5초로 시간초과가 빡빡한 문제다.

BFS/DFS 구현은 쉬운 문제지만 시간초과를 다루는 것이 어렵다. 

방문유무를 판별하는 리스트를 만들어 그래프를 탐색하면서 방문유무를 판단하면서 업뎃한다. 

시간초과가 나는 다른 코드들 보면 로직이 다 맞는데 종이한장 차이로 그런 결과가 나는 것 같다.

시간복잡도 비용을 최소화하는 로직 공부도 많이 해버릇해야겠다..

 

파이썬 코드

#1325_효율적인 해킹
from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
    q= deque()
    q.append(start)
    visited[start]=1
    
    while q:
        start = q.popleft()
        for i in rel[start]:
            if visited[i]==0:
                visited[i]=1
                q.append(i)

N, M = map(int, input().split())

rel = [[0] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    rel[b].append(a)

cnt = []
for i in range(1,N+1):
    visited = [0 for _ in range(N+1)] #init evry/time
    bfs(i)

    cnt.append(visited.count(1))

idx = 1
for i in cnt:
    if i==max(cnt):
        print(idx, end=" ")
    idx += 1