[BOJ] 효율적인 해킹 - 1325 (S1)

시간 제한	메모리 제한
5 초	256 MB

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, “A가 B를 신뢰한다”를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이

이 문제는 방향 그래프에서 각 노드로부터 도달 가능한 노드의 개수를 세는 문제이다.

접근 방법

핵심 아이디어

“A가 B를 신뢰한다” = “B를 해킹하면 A도 해킹할 수 있다”

즉, 간선의 방향을 역으로 저장하면:

• B → A로 저장
• B에서 BFS/DFS를 수행하면 해킹 가능한 모든 컴퓨터를 찾을 수 있음

풀이 과정

1. 간선을 역방향으로 저장 (B가 해킹당하면 A도 해킹됨)
2. 각 컴퓨터에 대해 BFS/DFS 수행
3. 도달 가능한 컴퓨터 개수 카운트
4. 최대 개수를 해킹할 수 있는 컴퓨터 출력

코드

import sys
from collections import deque

input = sys.stdin.readline
# print = sys.stdout.write

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

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

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

def search_hack(start):
    q = deque([start])
    visited = [False] * (N + 1)
    visited[start] = True
    cnt = 0

    while q:
        cur_com = q.popleft()
        cnt += 1
        for n_com in graph[cur_com]:
            if visited[n_com]:
                continue
            q.append(n_com)
            visited[n_com] = True
    
    return cnt

max_com_cnt = 0
result = []
total_visited = set()
for com in range(1, N + 1):
    com_cnt = search_hack(com)
    # print(com_cnt)
    if max_com_cnt < com_cnt:
        max_com_cnt = com_cnt
        result = [com]
    elif max_com_cnt == com_cnt:
        result.append(com)

print(*sorted(result))

코드 설명

역방향 그래프 구성

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

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

• “A가 B를 신뢰” = B → A 간선 추가
• B를 해킹하면 A도 해킹 가능

BFS로 해킹 가능한 컴퓨터 세기

def search_hack(start):
    q = deque([start])
    visited = [False] * (N + 1)
    visited[start] = True
    cnt = 0

    while q:
        cur_com = q.popleft()
        cnt += 1
        for n_com in graph[cur_com]:
            if visited[n_com]:
                continue
            q.append(n_com)
            visited[n_com] = True
    
    return cnt

• 시작 컴퓨터부터 BFS 수행
• 도달 가능한 모든 컴퓨터 카운트
• 자기 자신도 포함

최대값 찾기

max_com_cnt = 0
result = []
for com in range(1, N + 1):
    com_cnt = search_hack(com)
    if max_com_cnt < com_cnt:
        max_com_cnt = com_cnt
        result = [com]
    elif max_com_cnt == com_cnt:
        result.append(com)

print(*sorted(result))

• 각 컴퓨터에 대해 해킹 가능 개수 확인
• 최대 개수와 같은 모든 컴퓨터 저장
• 오름차순 정렬하여 출력

시간 복잡도

• 각 컴퓨터마다 BFS: O(N + M)
• 전체 N개 컴퓨터: O(N × (N + M))
• N ≤ 10,000, M ≤ 100,000
• 최악의 경우: 10,000 × 110,000 = 1,100,000,000

시간 제한이 5초이고, 파이썬은 초당 약 1억 번 연산이 가능하므로 통과 가능하다.

최적화

시간이 빡빡할 경우 다음 최적화를 고려할 수 있다:

1. 빠른 입출력: sys.stdin.readline() 사용
2. DFS 대신 BFS: 재귀 오버헤드 감소
3. 조기 종료: 이미 방문한 노드 재탐색 방지

주의 사항

1. 역방향 그래프: A→B가 아닌 B→A로 저장
2. 자기 자신 포함: 해킹한 컴퓨터 자신도 카운트에 포함
3. 오름차순 출력: 여러 개일 경우 정렬 필요
4. 빠른 입출력: N, M이 크므로 필수

문제 해석

이 문제는 “신뢰 관계”를 반대로 생각해야 한다:

• “A가 B를 신뢰” ≠ A를 해킹하면 B도 해킹됨 (X)
• “A가 B를 신뢰” = B를 해킹하면 A도 해킹됨 (O)

따라서 간선을 역방향으로 저장하고, 각 노드에서 출발하여 도달 가능한 노드를 세면 된다.