[BOJ / Python] 1325 효율적인 해킹

🧩 문제 : 1325번 효율적인 해킹

👩🏻‍💻 문제 정리 

해커가 컴퓨터 N개가 존재하는 회사를 해킹하려고 한다. 

컴퓨터 N개는 각각 M개의 신뢰 관계가 존재한다. 

위 예시를 보면, 회사에는 5개의 컴퓨터가 존재하고 4개의 신뢰 관계가 존재한다. 

각각의 신뢰 관계를 고려해보면 컴퓨터 1, 2를 해킹했을 때 3, 4, 5까지 해킹 할 수 있다.

 

💪🏻 해결 방법 

1️⃣ BFS 이용하기 

1. 신뢰하는 컴퓨터 인접 리스트 정의

n, m = map(int, input().split()) # n : 컴퓨터 개수, m : 연관관계 개수
graph = [[] for _ in range(n+1)] # 컴퓨터는 1 ~ n번까지 번호가 매겨져 있음

 

2. 전체 컴퓨터를 각각 BFS처리 (q가 빌 때 까지)

  - 신뢰받는 컴퓨터가 있으면, cnt += 1 하고 q에 append

  - cnt리턴하여 result 배열에 append

def bfs(v):
    queue = deque([v])
    cnt = 1
    visited = [False] * (n+1)
    visited[v] = True
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                cnt += 1
    return cnt

 

3. 배열에서 최댓값을 구하고 해당 값을 가진 인덱스 반환(컴퓨터는 1번부터 시작 주의)

max = max(result)
for i in range(len(result)):
    if max == result[i]:
        print(i+1, end=' ')

 

전체 코드 

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

def bfs(v):
    queue = deque([v])
    cnt = 1
    visited = [False] * (n+1)
    visited[v] = True
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                cnt += 1
    return cnt

n, m = map(int, input().split()) # n : 컴퓨터 개수, m : 연관관계 개수
graph = [[] for _ in range(n+1)] # 컴퓨터는 1 ~ n번까지 번호가 매겨져 있음

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

result = []
for i in range(1, n+1):
    result.append(bfs(i))

max = max(result)
for i in range(len(result)):
    if max == result[i]:
        print(i+1, end=' ')

 

🎁 성공!

근데 왜 같은 코드인데 PyPy3 만 맞는걸까 ..????????

 

간단한 코드상에서는 Python3가 메모리, 속도 측에서 우세할 수 있는 것이고,

복잡한 코드(반복)을 사용하는 경우에서는 PyPy3가 우세하기 때문에

-> 코드 상황에 맞추어 두 구현체(PyPy3, Python3)를 적절하게 사용하는 것이 효율적이라고 한다!

 

참고 : https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4