[Python] 백준 1325 - 효율적인 해킹

1325번: 효율적인 해킹

문제 설명

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

 

입력

• 첫째 줄: 총 컴퓨터의 개수 N, 신뢰 관계 개수 M
• 둘째 줄~: 컴퓨터 A, B(A는 B를 신뢰)

출력

한 번에 가장 많이 해킹할 수 있는 컴퓨터의 번호 오름차순으로 출력

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

풀이 방법

입력된 컴퓨터 A, B의 관계를 단방향으로 저장하고 BFS를 사용하여 방문해야 하는 노드의 개수를 컴퓨터별로 계산하고, 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 리스트에 저장한 뒤 출력한다.

*DFS 사용 시 시간 초과 발생

---

Python3/PyPy3

DFS (시간 초과)

from collections import deque
import sys
def dfs(graph, start_node):
    count=1
    visited = []
    need_visited = deque()
    need_visited.append(start_node)
    while need_visited:
        node = need_visited.popleft()
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
            count+=1
    return count

N, M=map(int, sys.stdin.readline().split())
graph=dict()
for i in range(N):
    graph[i+1]=[]

for _ in range(M):
    a, b=map(int, sys.stdin.readline().split())
    graph[b].append(a)

max=0
max_list=[]
for j in range(1, N+1):
    tmp=dfs(graph, j)
    if tmp>max:
        max=tmp
        max_list=[j]
    elif tmp==max:
        max_list.append(j)

print(*max_list)

BFS

from collections import deque
import sys
def bfs(start_node):
    visited=[0 for _ in range(N+1)]
    visited[start_node]=1
    need_visited=deque()
    need_visited.append(start_node)
    count=1
    while need_visited:
        node=need_visited.popleft()
        for i in graph[node]:
            if not visited[i]:
                need_visited.append(i)
                visited[i]=1
                count+=1
    return count

N, M=map(int, sys.stdin.readline().split())
graph=dict()
for i in range(N):
    graph[i+1]=[]

for _ in range(M):
    a, b=map(int, sys.stdin.readline().split())
    graph[b].append(a)

max=0
max_list=[]
for j in range(1, N+1):
    tmp=bfs(j)
    if tmp>max:
        max=tmp
        max_list=[j]
    elif tmp==max:
        max_list.append(j)

print(*max_list)