문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
출력
첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.
접근 방식
보자마자 그래프와 우선 탐색 알고리즘이 떠올랐다.
컴퓨터 A와 B간의 관계를 저장하고, bfs로 각각의 컴퓨터에서 부터 출발하여 더이상 해킹 가능한 컴퓨터가 없을 때 까지 탐색한다.
메모리 초과 이슈
해당 문제는 메모리 초과 문제로 인해 정답률이 낮은 편에 속한다. 나 또한 메모리 초과로 몇번 틀렸는데, 알아보니 파이썬이 아닌 PyPy3로 문제를 제출하면 수월하게 메모리 이슈를 해결할 수 있다고 한다.
PyPy3는 JIT컴파일러를 이용하기 때문에 복잡한 코드를 실행하는 데에 있어서 기존 파이썬보다 성능이 좋다고 한다. 자세한 내용은 다음에 알아봐야겠다.
PyPy3로 제출해도 메모리 초과문제가 해결되지 않았다.
컴퓨터간의 신뢰 관계를 딕셔너리로 저장했기 때문에 그런것으로 보인다.
# 컴퓨터의 A 와 B 관계를 딕셔너리로 정리
for _ in range(M):
A, B = map(int, input().split())
if B in dict:
dict[B].append(A)
else:
dict[B] = [A]정확하게는 모르겠지만 딕셔너리가 리스트보다 메모리 효율성이 떨어지는 것 같다.
comArr = [[] for _ in range(N+1)]
# 컴퓨터의 A 와 B 관계를 2차원 배열로 정리
for _ in range(M):
A, B = map(int, input().split())
comArr[B].append(A)컴퓨터의 관계를 2차원 배열로 바꿔서 저장해주었더니 결국 메모리 초과 이슈를 해결 할 수 있었다.
전체 코드
from collections import deque
import sys
input = sys.stdin.readline
# bfs
def graph(n):
queue = deque([n])
cnt = 0
visited = [0] * (N+1)
visited[n] = 1
while queue:
q = queue.popleft()
cnt += 1
# 해킹가능한 컴퓨터가 존재하지 않을 때 까지 탐색
for i in comArr[q]:
if not visited[i]:
queue.append(i)
visited[i] = 1
return cnt
N, M = map(int, input().split())
comArr = [[] for _ in range(N+1)]
# 컴퓨터의 A 와 B 관계를 2차원 배열로 정리
for _ in range(M):
A, B = map(int, input().split())
comArr[B].append(A)
# 각 컴퓨터마다 최대 해킹 가능한 컴퓨터의 수 저장
answer = [0 for _ in range(N+1)]
for i in range(1, N+1):
answer[i] = graph(i)
# 해킹 가능한 컴퓨터가 가장 많은 컴퓨터의 번호 출력
for i in range(1, N+1):
if answer[i] == max(answer):
print(i, end=' ')문제의 정답을 출력하는 것 자체는 어렵지 않았지만, 시간 초과, 메모리 초과를 해결하기 위해 많이 애를 먹었던 문제였다.
