🧩 문제 : 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
'알고리즘' 카테고리의 다른 글
[BOJ / Python] 앵무새 (1) | 2023.02.01 |
---|---|
[BOJ / Python] 1484 다이어트 (0) | 2023.01.30 |
[BOJ / Python] 2156 포도주 시식 (0) | 2023.01.20 |
다이나믹 프로그래밍 (0) | 2023.01.20 |
[BOJ / Python] 내일 할거야 (0) | 2023.01.16 |