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

2024년 8월 6일

문제 링크 : 백준 1325번 - 효율적인 해킹

 

문제

 

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

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

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

입력

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

출력

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

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

---

 

문제 접근

 

Python3로 채점하니 시간초과당해서 Pypy3로 채점했다.

 

정답율이 왜 이렇게 낮나 했더니 나와 같은 경우가 대부분이었다.. ( 시간 제한이 5초인데 왜지..? )

 

아무튼, 이 문제는 단방향 그래프에 대한 탐색 문제로, A가 B를 신뢰한다면 B를 해킹했을 때 A 또한 해킹할 수 있다는 의미이다.

 

그러므로, 입력값이 A B로 주어졌다면, B -> A라는 의미이다.

 

각 정점을 시작점으로 BFS를 수행하며 해당 정점을 시작점으로 하였을 때 가장 많은 컴퓨터로 이어지는 시작점을 출력하면 되며, 만약 그런 시작점이 여러 개라면 오름차순으로 출력해야 한다.

 

 

---

입력 예제

 

5 4
3 1
3 2
4 3
5 3

 

 

 

출력 예제

 

1 2

 

 

---

전체 코드

 

# 1325
import sys
from collections import deque
input = sys.stdin.readline

def bfs(start_v):
    cnt = 1

    queue = deque()
    visited[start_v] = True
    queue.append(start_v)

    while queue:
        now_v = queue.popleft()
        for next_v in relation[now_v]:
            if not visited[next_v]:
                visited[next_v] = True
                cnt += 1
                queue.append(next_v)
    return cnt

if __name__ == "__main__":

    N, M = map(int, input().split())
    relation = [[] for _ in range(N + 1)]


    for _ in range(M):
        a, b = map(int, input().split())
        # a가 b를 신뢰하면, b를 해킹했을 때 a 또한 해킹할 수 있음
        relation[b].append(a)

    max_cnt = 1
    result = []
    for start_v in range(1, N + 1):
        visited = [False] * (N + 1)
        cnt = bfs(start_v)
        if max_cnt == cnt:
            result.append(start_v)
        elif max_cnt < cnt:
            result.clear()
            max_cnt = cnt
            result.append(start_v)
    print(*result)

 

---

풀이 후기

 

시간복잡도가 O(V * (V + E)) 라서 5초 안에 돌아가겠지 했는데 아니어서 너무 슬펐다...