[Python] 백준 1325 효율적인 해킹 (BFS)

 

📌 문제

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

 

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

 

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

입력

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

출력

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

예제 입력 1

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2

 

---

 

📌 풀이

💬 Code

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


def bfs(node):
    q = deque([node])
    visited = [0] * (n + 1)
    visited[node] = 1
    cnt = 1
    while q:
        v = q.popleft()
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i] = 1
                cnt += 1
    return cnt


if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        a, b = map(int, input().split())
        graph[b].append(a)

    maximum = 0
    idx = []

    for i in range(1, n + 1):
        ret = bfs(i)
        if maximum < ret:
            idx = [i]
            maximum = ret
        elif maximum == ret:
            idx.append(i)

    print(*idx, sep=' ')

 

💡 Solution

A가 B를 신뢰할 때, B만 해킹하면 A도 해킹할 수 있습니다. 따라서 B의 연결 정보에 A를 넣어주는 단방향 그래프로 구현해주면 됩니다. 우리는 B를 해킹했을 때 몇 개의 컴퓨터를 해킹할 수 있는지 'B의 연결 정보'만 필요하기 때문입니다. A의 연결 정보는 이 문제에선 필요가 없습니다.

 

bfs(i)함수에 cnt 정보를 추가해 i를 해킹하면 몇 개의 컴퓨터를 덤으로 해킹할 수 있는지 i와 연결된 컴퓨터의 갯수인 cnt를 반환합니다.

bfs(i)함수를 여러번 호출하면서 cnt를 비교해야 하므로, visited 배열의 선언을 main함수가 아닌 bfs(i)함수 안에 하여 bfs가 호출될 때마다 방문 정보를 초기화해주어야함에 주의해야 합니다.

 

Python3과 Pypy3의 차이

Python3으로 제출하면 시간초과가 나기 때문에 Pypy3으로 제출해야 했습니다. 둘이 뭐가 다른지 궁금해 찾아봤습니다. 🤔

 

• PyPy3는 실행시 자주 쓰이는 코드를 캐싱하는 기능이 있기 때문에, 즉 메모리를 Python3보다 조금 더 사용하면서 이 코드를 저장하고 있어 실행속도를 개선할 수 있습니다.

 

• 간단한 코드는 Python3가 메모리, 속도 측에서 우세하고
  복잡한 코드, 주로 반복을 사용하는 경우에서는 PyPy3가 우세하기 때문에
  코드 상황에 맞추어 둘을 적재적소에 사용하는 것이 효율적입니다! 💡

 

defaultdict()

다른 분들은 어떻게 푸셨을까 궁금해서 찾아보는데 graph를 defaultdict로 선언한 풀이가 많이 보였습니다. defaultdict는 처음 보는 아이라 궁금증이 도져서 직접 돌려봤습니다 🤔

• defaultdict 사용 X

graph = [[] for _ in range(n + 1)]
…
print(graph)
# 출력결과 [[], [3], [3], [4, 5], [], []]

연결정보가 없는 컴퓨터의 경우 빈 리스트 []로 남습니다.

• defaultdict 사용 O

from collections import defaultdict
graph = defaultdict(list)
…
print(graph)
# 출력결과 defaultdict(<class 'list'>, {1: [3], 2: [3], 3: [4, 5]})

연결정보가 없는 컴퓨터의 경우 아예 key: value set조차 생성되지 않습니다.
아직 어느 상황에서 쓰면 좋을지 감은 잡힐랑말랑인데 좋은 접근을 알게 된 것 같습니다!