[백준 1325번] 효율적인 해킹 - 파이썬

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

💡문제 분석 요약

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

 

💡알고리즘 설계

큐를 이용한 BFS로 구현했다.

 

1. 한 컴퓨터가 해킹할 수 있는 컴퓨터의 리스트를 저장한다.

2. 모든 컴퓨터에서 bfs를 실행한다.

2-1. 해당 컴퓨터가 해킹할 수 있는 리스트를 큐에 넣고, 첫번째 노드를 반환한다. 그 노드를 방문처리 한 후, 그 노드가 해킹할 수 있는 컴퓨터들을 큐에 추가한다. 큐가 빌 때 까지 반복한다.

3. 최대값을 저장한 후 카운트 리스트에서 최대값과 같은 컴퓨터만 출력한다.

 

5 4
3 1
3 2
4 3
5 3

입력이 위와 같을 경우, 그래프는

[ [3], [3], [4, 5], [], [5] ] 가 된다.

 

💡코드

import sys
from collections import deque
input = sys.stdin.readline

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

graph=[[] for _ in range(N+1)]

for _ in range(M):
    target, start=map(int,input().split())
    graph[start].append(target)

def bfs (node):
    queue = deque([node])
    visited = [False for _ in range(N+1)]
    visited[node] = True
    count=1
    
    while queue:
        a = queue.popleft()
        for i in graph[a]:
            if not visited[i]:
                visited[i] = True
                count+=1
                queue.append(i)
    return count

countList=[0 for _ in range(N+1)]
for i in range(1,N+1):
    countList[i]=bfs(i)

maxCount=max(countList)
for i in range(1,N+1):
    if countList[i]==maxCount:
        print(i, end=' ')

 

💡 느낀점 or 기억할 정보

실수로 visited를 dfs와 헷갈려서 전역변수로 지정하는 바람에 메모리초과가 났다.

python3으로 제출했는데 시간초과가 나왔다. 확인해보니 phython3으로 통과한 사람이 없고 모두 pypy를 이용해서 통과했길래 나도 pypy를 이용해서 제출했더니 통과했다.. ㅎㅎ