[211115] 백준 1325 효율적인 해킹 실버2 문제풀이 python

 

- 알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

---

 

 

# 백준 1325 효율적인 해킹 실버2

import sys
import collections
input = sys.stdin.readline

def bfs(start):
    cnt = 1
    visited = [0 for _ in range(N+1)]
    visited[start] = 1
    queue = collections.deque([start])

    while queue:
        u=queue.popleft()
        for v in com[u]:
            if not visited[v]:
                queue.append(v)
                visited[v]=1
                cnt += 1
    return cnt

N, M = map(int,input().split()) # 컴퓨터 N, 관계 M
com = [[]for _ in range(N+1)]

for i in range(M):
    a,b = map(int,input().split()) # 신뢰관계 a b(a가 b를 신뢰,b는 a를 해킹 가능)
    com[b].append(a) #b가 접근할 수 있는 리스트

results = []
max_cnt = 0
for i in range(1, N+1):
    cnt=bfs(i)
    if(cnt > max_cnt):
        max_cnt = cnt
    results.append([i,cnt])

for i, cnt in results:
    if cnt == max_cnt:
        print(i,end = ' ')

 

 

 

pypy3는 Cpython의 느린 속도를 개선하기 위해 JIT 컴파일러를 도입한 것으로 자주 사용하는 코드를 캐싱하기 때문에 단순한 코드는 python을 복잡한 코드(반복)는 pypy3를 사용하는 것이 성능 면에서 더 좋다고 한다.

https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4

 

 

 

---