[백준] 1325 파이썬(python) : 효율적인 해킹 - (★)

1325번: 효율적인 해킹

 

 

 

pypy3로 제출하면 정답처리가 됩니다.

 

 

from collections import deque
import sys
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) #1
ans = []

def bfs(v, visit):
    q = deque([v])
    count = 0
    while q:
        x = q.popleft()
        for nx in graph[x]:
            if not visit[nx]:
                visit[nx] = True
                count += 1
                q.append(nx)
    return count

max_cnt = 0
for i in range(1, n+1):
    visit = [False] *(n+1)
    visit[i] = True
    cnt = bfs(i, visit)
    if max_cnt < cnt: #2
        max_cnt = cnt 
    ans.append((cnt, i)) #3

for cnt, i in ans: #4
    if cnt == max_cnt:
        print(i, end=' ')

 

 

#1 : 입력값이 1 3 일때 1번 컴퓨터가 3번 컴퓨터를 신뢰한다고 했으니까 graph[b].append(a)로 해서 bfs일때 3번 노드를 거쳐 1번 노드로 가야한다.

#2 : 리턴값 중 가장 큰 값을 저장하는 변수

#3 : 입력값 중 가장 큰 값의 번호만 출력

 

 

사실대로 말하면 bfs와 visit 리스트가 bfs를 실행할때마다 초기화 해주는 것 까지 구현하고 막혔습니다. 최대값이 2개일때 출력하는 법을 몰라서 블로그를 찾았습니다. 다행히 나랑 비슷한 풀이를 가진 블로그를 찾을 수 있었고 마지막 부분만 조금 도움을 받아 해결할 수 있었습니다.

 

 

제가 생각한 방법은 ans.sort(reverse=True)였는데 이러면 최고값 1개만 출력이 가능합니다.