[Python] 백준 1325번 - 효율적인 해킹 (실버 1)

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

1325번: 효율적인 해킹

 

혼자 힘으로 풀었는가? x

알고리즘 분류
 - DFS
 - BFS

 

문제

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

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

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

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

---

 

BFS/DFS로 풀면되겠네 쉽네

 

하고 풀러 들어가면 '시간초과' 를 보게 된다.

 

시간초과 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = [ [0]for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    data[b].append(a)
    
cnt = [0] * (n+1)

from collections import deque
def bfs(n):
    q = deque()
    q.append(n)
    visited[n] = 1
    cnt = 0
    
    while q:
        now = q.popleft()
        size = len(data[now])
        if size != 0:
            cnt += size-1
            for i in range(1, size):
                if visited[data[now][i]] == 0:
                    q.append(data[now][i])
                    visited[now] = 1
    return cnt
                

for i in range(1, n+1):
    visited = [0] * (n+1)
    cnt[i] = bfs(i)
    
k = max(cnt)
for i in range(1, n+1):
    if k == cnt[i]:
        print(i, end=' ')

 

정답 코드 (PyPy3 제출)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = [ [] for _ in range(n+1)]
cnt = [0] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    data[b].append(a)
    
from collections import deque
def bfs(n):
    q = deque()
    q.append(n)
    visited[n] = 1
    
    while q:
        now = q.popleft()
        cnt[n] += 1
        for i in data[now]:
            if visited[i] == 0:
                visited[i] = 1
                q.append(i)
    
result = -1    
resultList = []

for i in range(1, n+1):
    visited = [0] * (n+1)
    bfs(i)
    
    if cnt[i] > result:
        resultList = []
        result = cnt[i]
        resultList.append(i)
    elif cnt[i] == result:
        resultList.append(i)
        
for i in resultList:
    print(i, end=' ')

솔직히.. 큰 차이는 없어 보이는데... 

 

최대 값을 찾는 과정에서 배열에 계속 쌓아서 다시 찾는 것과 초기화하며 최대 값만 넣는 것의 차이라고 볼 수 있다.