[파이썬/Python] 백준 1325번: 효율적인 해킹

숨·2024년 7월 15일

코테

알고리즘 문제 풀이

목록 보기

32/105

📌 문제 : 백준 1325번

📌 문제 탐색하기

N : 컴퓨터 수 (1 ≤ N ≤ 10,000)
M : 컴퓨터 간 관계 (1 ≤ M ≤ 100,000)

✅ 입력 조건
1. N,M 공백으로 구분해 입력
2. M번 반복해 연결 정보 입력
3. A가 B를 신뢰한다 = B 해킹하면 A 해킹 가능
✅ 출력 조건
1. 한 번에 가장 많은 컴퓨터 해킹할 수 있는 컴퓨터 번호 출력

N개의 컴퓨터 간 연결 정보를 이용해 가장 많이 해킹할 수 있는 컴퓨터를 찾는 문제이므로 이전에 풀었던 바이러스 문제에 여러 가지 조건이 추가적으로 붙은 문제 같다.

A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리라고 했으므로 컴퓨터 간 연결 관계는 B → A로 가는 단방향 그래프로 저장한다.

컴퓨터 별로 연결된 컴퓨터 수를 저장할 리스트를 따로 정의한다.

DFS/BFS를 정의해서 해당 컴퓨터와 연결된 모든 컴퓨터를 탐색하면서 count를 1씩 증가시키고, 탐색 후엔 그 count 값을 따로 저장한다.

최종적으로 얻은 count 리스트에서 최댓값을 구해 그 값을 가지는 컴퓨터를 출력한다.

가능한 시간복잡도

그래프 저장 → $O(M)$
모든 컴퓨터에서 BFS → $O(N * (N + M))$

최종 시간복잡도
$O(N * (N + M))$ 이므로 최악의 경우 $O(10,000 * 110,000) = O(1,100,000,000)$ 로 5억번 내로 계산이 가능할 것 같다.

알고리즘 선택

BFS로 연결 노드 탐색하기

📌 코드 설계하기

N, M 입력
연결 정보 저장 리스트 정의
컴퓨터 별로 연결 컴퓨터 수 저장할 리스트 정의
DFS/BFS 정의
DFS/BFS 수행
최대 해킹 가능 컴퓨터 수 계산
정답 저장 리스트 정의
원하는 결과 출력

📌 시도 회차 수정 사항

1회차

# DFS 정의
def dfs(start, visited):
    count = 1               # 개수 세기
    visited[start] = 1      # 방문 처리
    for i in graph[start]:
        if not visited[i]:
            count += dfs(i, visited)
    return count

결과
DFS를 재귀적으로 동작하도록 구현하였다. 예제는 잘 작동했으나 제출하니 시간 초과가 발생했다.

def bfs(start, visited):
    queue = deque([start])
    count = 0  # 개수 세기
    visited[start] = 1  # 방문 처리

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 원소 하나 뽑기
        v = queue.popleft()
        count += 1
        # 해당 원소와 연결된 방문 안한 원소 큐 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1
    return count

결과
시간 초과를 해결하기 위해 BFS로 구현해보았지만, 여전히 시간 초과가 났다.

2회차

질문 게시판을 참고해보니 Python3으로 통과하기 어려워 PyPy3를 이용하신 분들이 많았다. 나 또한 PyPy3로 제출하니 정답 처리가 되었다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# BFS 정의
def bfs(start):
    queue = deque([start])
    visited = [0] * (N + 1)
    count = 0  # 개수 세기
    visited[start] = 1  # 방문 처리

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 원소 하나 뽑기
        v = queue.popleft()
        count += 1
        # 해당 원소와 연결된 방문 안한 원소 큐 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1
    return count

# N, M 입력
N, M = map(int, input().split())

# 연결 정보 저장 리스트 정의
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    # 연결 정보 입력
    A, B = map(int, input().split())
    # 단방향이니까 B에 A 추가
    graph[B].append(A)

# 컴퓨터 별로 연결된 컴퓨터 저장할 리스트 정의
connections = [0] * (N + 1)

# BFS 수행
for i in range(1, N + 1):
    connections[i] = bfs(i)

# 최대 해킹 가능 컴퓨터 수 계산
max_count = max(connections)

# 정답 저장 리스트 정의
answer = [i for i in range(1, N + 1) if connections[i] == max_count]

# 원하는 결과 출력
print(*answer)