[BOJ] 1325 효율적인 해킹 (Python3)

문제

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

풀이

간단한 탐색문제로 bfs로 풀 수 있는데, 컴퓨터의 신뢰관계를 노드 형식으로 리스트에 넣어주고, 노드가 많이 연결되어있는 컴퓨터순으로 출력하면 된다.

코드

from collections import deque
#컴퓨터의 개수 n, 신뢰관계의 개수 m
n,m = map(int, input().split())

#노드의 형태 graph
graph = [[] for _ in range(n+1)]

#자신을 신뢰하는 컴퓨터를 자신의 리스트에 넣는다
for i in range(m):
    a,b = map(int, input().split())
    graph[b].append(a)

#bfs를 사용하여 1-5의 컴퓨터를 순서대로 방문하며, 자신을 신뢰하는 컴퓨터에 모두 방문한다.
#방문한 횟수를 hack 변수에 넣는다.
def bfs(x):
    q = deque()
    q.append(x)
    hack = 1
    visited = [0 for _ in range(n+1)]
    visited[x] = 1
    while q:
        nx = q.popleft()
        for i in graph[nx]:
            if visited[i] == 0:
                q.append(i)
                hack+=1
                visited[i] = 1
    return hack
#자신을 신뢰하는 컴퓨터의 개수를 저장하는 리스트 answer
answer = []
#bfs함수에 넣어 얻은 result를 answer 리스트에 넣어준다.
for i in range(1,n+1):
        answer.append(bfs(i))
    
    
#resutl 순차 출력
for i in range(len(answer)):
    if max(answer)== answer[i]:
        print(i+1, end = ' ')

5 4
3 1
3 2
4 3
5 3
1 2 

Feedback

방문을 체크하는 visited 리스트를 만들지 않아서 계속 메모리 초과가 떴다.
예제는 서로 상호신뢰관계가 없어서 잘되길래 문제가 없다고 생각했는데, 테스트셋의 상호신뢰관계 때문에 반복이 끝나지를 않아서 메모리가 초과 된것 같다.
bfs, dfs를 풀때는 항상 방문을 잘 체크하자.