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

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

1325번: 효율적인 해킹

 

# 조건

• N개의 컴퓨터로 구성된 회사를 해킹하는데, 각각의 컴퓨터 중엔 신뢰하는 관계가 존재한다.
• A -> B 컴퓨터를 신뢰하는 관계라면, B 컴퓨터만 해킹하여도 A는 자동으로 해킹된다.
• 이 때, 한 컴퓨터를 해킹해서 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 출력하여라!
• 여러 대가 있다면, 오름차순 출력

 

# 접근 방법

• 자식 노드만 확인하는 것이 아닌 그 컴퓨터를 '신뢰하는' 또 다른 컴퓨터까지 확인해 주어야한다.
• 따라서 BFS를 확인하여 각 컴퓨터마다 해킹가능한 컴퓨터 수를 기록해주고 가장 많이 해킹하는 컴퓨터를 출력한다.
• BFS 기본 예제 문제와 비슷해보이지만, 1번이 아닌 모든 컴퓨터를 체킹한다는 것이 다르다.
• 그러다보니 많은 메모리, 시간을 사용하게 되고 PyPy로 제출하지 않는 이상 통과가 힘들었다..

```python
# N개의 컴퓨터 중 A가 B를 신뢰한다면 B해킹 시 A도 해킹 가능  
# 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호 출력  
import sys  
from collections import deque  
input = sys.stdin.readline  
  
# 시작 넘버를 함수의 변수로 받아준다.  
def hacking(num):  
   count = 1  
   # 방문기록  
   visited = [0] * (N+1)  
   visited[num] = 1  
   # deque 모듈을 활용  
   q=deque([num])  
  
   while q:  
      # 방문할 컴퓨터 번호 변수  
      com = q.popleft()  
      # 자신을 신뢰하는 컴퓨터가 있는지 확인하는 반복문  
      for i in trust[com]:  
         # 아직 방문하지 않았다면 -> 나를 신뢰하는 컴퓨터'를' 신뢰하는 컴퓨터를 체크하기 위한 조건문  
         if not visited[i]:  
            visited[i] = 1  
            count += 1  
            q.append(i)  
   return count  
  
  
  
N, M = map(int, input().split())  
# 신뢰관계 기록  
trust = [[] for _ in range(N+1)]  
# a->b 구조로 신뢰하므로 b에 a의 번호를 기록해준 후 b를 해킹시 a도 해킹 할 수 있다로 생각  
for i in range(M):  
   a, b = map(int, input().split())  
   trust[b].append(a)  
  
# 해킹한 컴퓨터 수 기록  
count = 0  
  
  
# max count  
max_count = 0  
# 최고 해킹 수 기록 리스트  
max_hacking = [0]  
for i in range(1, N+1):  
   count = hacking(i)  
   # 현재 최고 해킹 수를 기록해준 후 리스트비운 후 새로 추가해준다.  
   if count > max_count:  
      max_count = count  
      max_hacking.clear()  
      max_hacking.append(i)  
   # 동일하다면 그냥 추가  
   elif count == max_count:  
      max_hacking.append(i)  
  

print(*max_hacking)

• 역시나 메모리, 시간 초과의 문제로 인하여 스트레스를 주는 문제였다..
• 전체 컴퓨터의 신뢰관계를 보여주는 리스트를 만들어서 활용하려 하였지만, 메모리 초과가 발생하여 단순히 [신뢰관계에 있는 컴퓨터 번호] 만을 기록해주었다.
• 최대한 단순히, 필요없는 부분은 사용하지 않도록 로직을 잘 짜보는 것이 중요하다고 또 한번 느끼게 되었다!