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

문제 출처 : https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

잃어버린 감을 찾기위해 BFS 문제 풀이,,,
시간 초과로 pypy3로 제출

 

🔥 첫 제출 코드 (시간 초과)

def sol(n):
    global max_count, result

    tmp = [0] * (N+1)
    tmp[n] = 1

    queue = [n]
    while queue:
        s = queue.pop(0)
        for e in arr[s]:
            if tmp[e] == 0:
                tmp[e] = 1
                queue.append(e)

    N_count = sum(tmp)    
    if max_count == N_count:
        result.append(n)
    elif max_count < N_count:
        max_count = N_count
        result = [n]
    return


N, M = map(int, input().split())

arr = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    arr[b].append(a)

max_count = 0
result = []

for i in range(1, N+1):
    sol(i)

print(' '.join(str(i) for i in result))

⭕ 해설

1. 간단하게 연결 관계를 arr에 정리합니다.

2. 오름차순 정렬이므로 1번 컴퓨터부터 sol 함수에 대입합니다.

3. tmp를 visited 배열로 활용합니다.

4. BFS 활용 tmp에 해킹 컴퓨터 기록합니다.

5. 최대값과 비교하며 result를 구성합니다. 

 

 

시간초과 해결

from collections import deque

queue = deque([n])

데크를 활용하여 시간 단축하여 해결되었습니다...