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

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 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

제출 답안

• 리스트와 set의 메모리 사용량 차이
  • 신뢰하는 컴퓨터를 저장할 때 set은 계속 메모리 초과가 발생하여 이유를 찾아보았다.

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

def bfs(graph, start, n):
    cnt = 1
    q = deque([start])
    # 중복이 있을 경우 방문 여부
    visited = [False for _ in range(n+1)]
    visited[start] = True

    while q:
        # 현재 큐에 들어간 것중 맨 처음 값 pop
        cur = q.popleft()
        # cur을 신뢰하는 모든 컴퓨터 탐색
        for nx in graph[cur]:
            # 처음 방문하는 곳이라면
            if not visited[nx]:
                # 방문했다고 변경하고
                visited[nx] = True
                # 컴퓨터 숫자를 1개 증가
                cnt += 1
                # q에 삽입
                q.append(nx)
    return cnt

def solution():
    n,m = map(int,input().split())
    graph = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = map(int,input().split())
        # 여기서 set을 사용하면 메모리에서 엄청난 사용으로 리스트 사용해서
        # 방문 여부를 확인하는 방법이 더 효율적
        graph[b].append(a)
    # 최댓값 확인
    max_cnt = 1
    answer = []
    for i in range(1,n+1):
        cnt = bfs(graph, i, n)
        # cnt가 최댓값 보다 크면
        if cnt > max_cnt:
            # 최댓값을 cnt로
            max_cnt = cnt
            # 지금까지의 answer는 cnt보다 작기 때문에 초기화하고
            answer.clear()
            # cnt를 다시 새롭게 append
            answer.append(str(i))
        # 최댓값이랑 같으면 append
        elif cnt == max_cnt:
            answer.append(str(i))

    print(" ".join(answer))
solution()