백준 1325 - 효율적인 해킹 (Python3)

코드

Pypy3 정답

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())

    # a가 b를 신뢰한다 => b를 해킹하면 a도 해킹된다
    # ==> b에서 a로만 방향이 있는 단방향 그래프이다!!!
    graph[b].append(a)

# 각각의 컴퓨터에서 해킹 가능한 개수를 담을 리스트
result = [0]

# BFS 수행
def bfs(v):
    q = deque()
    q.append(v)
    
    visited = [False for _ in range(n+1)]
    visited[v] = True
    
    # 해킹 가능한 컴퓨터의 수를 담을 변수
    cnt = 0
    
    while q:
        nv = q.popleft()
        
        for i in graph[nv]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                
                # 해킹 하나 했으므로 +1
                cnt += 1
                
    # deque가 비면 cnt 반환            
    return cnt

# 각 컴퓨터에 대하여 bfs 수행 후, 그 결과를 result에 저장
for i in range(1, n+1):
    result.append(bfs(i))

# result 중 가장 큰 값의 인덱스 번호를 출력 => 컴퓨터의 번호 오름차순 출력하라는 조건과 일치
for i in range(len(result)):
    if result[i] == max(result):
        print(i, end = ' ')

문제 해설

전형적인 BFS 문제.

이 문제는 Pypy3을 사용하지 않으면 시간 초과에서 벗어나지 못하였다 ㅠㅠ…

문제 자체의 풀이는 간단하나 문제 자체를 이해하기 힘들 수 있는 부분이 있다.

---

* A 컴퓨터가 B 컴퓨터를 신뢰하는 경우, B 컴퓨터를 해킹하면 A 컴퓨터도 해킹할 수 있음*

---

위의 조건이 의미하는 바는 결국 B 컴퓨터에서 A 컴퓨터만으로의 이동이 가능하다는 의미이므로 B => A의 단방향 그래프가 주어진다는 뜻과 같다. 따라서

for _ in range(m):
    a, b = map(int, input().split())

    # a가 b를 신뢰한다 => b를 해킹하면 a도 해킹된다
    # ==> b에서 a로만 방향이 있는 단방향 그래프이다!!!
    graph[b].append(a)

그래프의 입력이 위와 같은 방식으로 이루어진다.

이를 제외하곤 별 다른 어려움 없이 풀 수 있는 문제였으나, 시간 초과를 해결할 수 있는 방법 또한 참고하여 다시 한 번 풀어봐야겠다.