boj.kr/1325 효율적인 해킹 (silver1) 파이썬 풀이

dfs으로 풀이 시도했으나 시간초과 났고, 시간초과가 나지 않더라도 테스트 케이스 범위로 인해 순환함수 호출 최대 제한에 걸릴 수 밖에 없다. bfs 방식으로 탐색하고 PyPy3으로 제출해야 한다.

 

시간초과난 dfs 풀이

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]


for i in range(M):
    (e, s) = map(int, input().split())
    graph[s].append(e)


def dfs(node):
    global cnt
    for nxt in graph[node]:
        if not visited[nxt]:
            visited[nxt] = True
            dfs(nxt)
            cnt +=1

cnt_list = []
for i in range(1, len(graph)):
    visited = [False] * (N + 1)
    cnt = 0
    dfs(i)
    cnt_list.append((i, cnt))

cnt_list.sort()
for (i, c) in cnt_list:
    if c == cnt_list[0][1]:
        print(i, end=" ")
    else:
        break

 

 

정답 풀이

1. 신뢰하는 관계를 저장하되 인덱스 번호를 신뢰하는 컴퓨터 번호, 요소 목록을 해당 컴퓨터 번호로부터 신뢰를 받는 컴퓨터 번호들의 목록으로 저장한다. 

2. 모든 컴퓨터 번호들에 대해 bfs 방식으로 방문 가능한 컴퓨터 번호의 총 개수를 카운트한다.

3. 최대로 방문 가능한 컴퓨터 번호들을 오름차순으로 출력한다.

N, M = map(int, input().split())
R = [[] for _ in range(N+1)]

for _ in range(M):
    (e, s) = map(int, input().split())
    R[s].append(e)

from collections import deque

def bfs(start_node):
    dq = deque()
    dq.append(start_node)
    chk[start_node] = 1
    while dq:
        cur = dq.popleft()
        for nxt in R[cur]:
            if chk[nxt] == 0:
                chk[nxt] = 1
                dq.append(nxt)
    return sum(chk)

tot_list = [0] * (N+1)
for sn in range(1, N+1):
    chk = [0] * (N+1)
    tot_list[sn] = bfs(sn)

for i in range(1, N+1):
    if tot_list[i] == max(tot_list):
        print(i, end=" ")

 

시간과 메모리를 절약하기 위해서 리스트의 인덱스 번호를 노드 번호로 활용해야 한다.