[BOJ] 1325번 - 효율적인 해킹(deque, list 고찰)

요즘 알고리즘들이 잘 안 풀리곤해서 몇 번 끄적이다 만 문제들이 많았다.

다시 마음먹고 천천히 쉬운문제부터 풀어볼까 하다가 이 문제에서부터 막혔다.. ㅋ.ㅋ 

하지만, 이 문제에서 deque의 효율성을 알 수 있는 계기가 되었다. 

 

글쓴이는 항상 bfs 구현 때마다 대수롭지 않게 queue를 list로 구현하곤 했다.  그 이유는 list역시 deque구조와 비슷하게 

원형 큐로 이루어 졌다고 생각했다. 이 문제를 풀기 전까지는....

 

조만간 깃에 각 리스트와 스트링 method의 Big-O 개념을 정리해야 될 것 같다.

단순한 bfs문제인 줄 알았던 문제에서 시간초과나는 이유를 알아버렸으니 deque를 이용해서 푸는 건 금방이였다.

 

나는 얼마나 시간초과가 나는지 계산해보고 싶어 time 함수를 이용해 제일 앞 list를 10만번 pop()한 시간을 구했다.

 

from sys import stdin
from collections import deque
from math import floor
import time

N = 100000
queue = [0 for i in range(N)]
deque = deque()
for i in range(N):
    deque.append(i)

start = time.time()
while queue:
    queue.pop(0)
end = time.time()
print(floor((end-start)*1000), "ms")

start = time.time()
while deque:
    deque.popleft()
end = time.time()
print(floor((end-start)*1000), "ms")

 

출력 값

2번 돌린 결과

여러번 돌려봤을 때 deque는 6~7ms 정도 나왔고, list를 pop(0)시켰을 땐 900~980ms가 나왔다.

차이는 무려 100배 이상이 나왔다. 간선이 10만개라고 생각해보면 시간복잡도는... ㅋ.ㅋ

 

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

문제는 단순 bfs 문제라 설명은 간단하게 하겠다.

 

1. (a 가 b를 신뢰할 때, b를 해킹하면 a를 해킹할 수 있다는 말)의 의미는 b를 check 한 이 후 b 주변 노드들을 해킹 할 수 있다는 말이 된다.

 

2. 각 정점을 기준으로 bfs 알고리즘을 돌린다.

 

from sys import stdin
from collections import deque

std = stdin.readline
N, M = map(int, std().split())
computer = [[] for i in range(N)]

for i in range(M):
    a, b = map(lambda x: int(x)-1, std().split())
    computer[b].append(a)

q = deque()


def bfs():
    check = [0 for i in range(N)]
    check[q[0]] = 1
    cnt = 0
    while q:
        vertax = q.popleft()
        for v in computer[vertax]:
            if check[v] == 0:
                check[v] = 1
                cnt += 1
                q.append(v)

    return cnt


answer = []
for i in range(N):
    q.append(i)
    answer.append(bfs())

max_ = max(answer)

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