효율적인 해킹 ( 1325 번 )

1325번: 효율적인 해킹

 

🧠 알고리즘

- 모든 노드에 대해 BFS를 돌려서, 각 노드로부터 해킹 가능한 컴퓨터 수를 구함.
- BFS를 돌리면서 visit 배열을 사용해 방문 체크.
- 각 노드의 해킹 수를 score_dict에 저장.
- 그 중 가장 많이 해킹한 개수를 기준으로 answer 리스트 구성 후 출력.

 

🧾 코드

import sys
from collections import deque

def _mk_conn():
    answer = {i: [] for i in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().rstrip().split())
        answer[b].append(a)
    
    return answer


def _main(conn_dict):
    answer = []
    score_dict, max_value = {}, 0
    for k, v in conn_dict.items():
        visit, count = [False] * n, 0
        visit[k - 1] = True
        count += 1
        queue = deque([k])

        while queue:
            now_point = queue.popleft()
            for next_point in conn_dict[now_point]:
                if not visit[next_point - 1]: # 아직 미방문
                    queue.append(next_point)
                    count += 1
                    visit[next_point - 1] = True

        max_value = max(max_value, count)
        score_dict[k] = count

    
    for k, v in score_dict.items():
        if v == max_value:
            answer.append(k)

    answer.sort() # 오름차순 정렬

    return ' '.join(map(str, answer))


n, m = map(int, sys.stdin.readline().rstrip().split())
conn_dict = _mk_conn()

print(_main(conn_dict))

 

⏱️ 시간 복잡도

for k, v in conn_dict.items() : 모든 간선을 탐색 ( 선형 시간 복잡도 )
	while queue : BFS 알고리즘 ( 선형 시간 복잡도 )
    
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )