[백준 1325번] 효율적인 해킹 (python)

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

 

기록

(graph 2일차) 초과때문에 너무 힘들었다.......................... 재귀로 dfs 구현해서 풀면 안된다고 한다. 정확히는 모르겠지만 시간초과가 아니어도 파이썬 최대 깊이를 초과한다는 것 같다.

 

그래서 스택을 사용한 dfs를 구현해서 해결했다. 모든 출발노드에서 dfs를 수행해서 방문한 노드 개수 합를 저장한다.

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

n, m = map(int, input().split())
edges = [[] for i in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    edges[b].append(a)

def dfs(x):
    visit = [0]*(n+1)
    visit[x] = 1
    stack = [x]
    while stack:
        com = stack.pop()
        for c in edges[com]:
            if not visit[c] :
                visit[c] = 1
                stack.append(c)
    return sum(visit)

com = [dfs(i) for i in range(1, n+1)]
_max = max(com)
for i in range(n):
    if com[i]==_max : print(i+1, end=' ')

1. 변수와 엣지정보 저장

2. 스택에 인접노드 저장해나가면서 visit에 방문한 노드 표시하고 최종적으로 방문한 노드들의 합을 반환하는 함수 구현

3. 모든 출발점에서의 가능한 방문노드 합을 저장해 최댓값인 노드들의 번호를 출력한다.