[Python] 1325. 효율적인 해킹

문제

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

---

풀이 과정

주어진 컴퓨터의 신뢰 관계를 인접 리스트로 만들어, 어떤 컴퓨터에서 가장 많이 다른 컴퓨터에 방문할 수 있을지를 세어 비교하면 간단히 풀 수 있는 문제였다. 

A가 B를 신뢰한다고 했으므로, B → A로만 방문할 수 있음에 유의해야 한다. (A → B로는 방문할 수 없음)

N이 최대 10,000이므로 DFS로 풀게 되면 RecursionError를 만나게 된다. 재귀 한도를 풀어주어도 메모리 초과가 난다. 따라서 BFS를 활용하여 문제를 해결할 수 있었다. 

코드 과정은 다음과 같다. 

1. 주어진 값들을 받고, 컴퓨터의 신뢰 관계는 인접 리스트로 만든다.
2. n개의 컴퓨터에서 차례로 bfs함수에 들어가 몇 개의 컴퓨터를 해킹할 수 있는지 센다.
   2-1. 인자로 전달받은 컴퓨터(시작 컴퓨터)부터 queue에 넣고 시작하여 while문을 돈다.
   2-2. queue에서 방문할 컴퓨터를 뽑는다.
   2-3. 해당 컴퓨터(now)에서 해킹할 수 있는 컴퓨터(방문할 수 있는 컴퓨터)(nxt) 중, 아직 해킹되지 않은(방문 처리되지 않은) 컴퓨터라면 count 하고 방문처리 후, 다음 컴퓨터에서 또 해킹하기 위해 queue에 넣어준다.
   2-4. 2-2와 2-3을 queue가 빌 때까지 반복한다. while 문이 끝나면 해킹된 컴퓨터의 수(방문한 컴퓨터 수)를 return 한다.
3. 해킹된 컴퓨터의 수가 이전 컴퓨터가 해킹한 컴퓨터의 수보다 많다면 정답 리스트를 초기화시키고, 수가 같다면 정답 리스트에 추가시킨다.

---

코드

from collections import deque

def bfs(s):
    visited = [0 for _ in range(n+1)]	
    visited[s] = True

    queue = deque([s])
    while queue:
        now = queue.popleft()

        for nxt in graph[now]:
            if not visited[nxt]:	# 아직 해킹하지 않은 컴퓨터라면 
                visited[nxt] = True	# 해킹한 컴퓨터 방문처리 
                queue.append(nxt)

    # 방문한 곳 => 해킹한 컴퓨터 이므로 방문 개수를 반환
    return sum(visited)


n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    com1, com2 = map(int, input().split())
    graph[com2].append(com1)    # com2에서 com1을 감염 시킬(방문 할) 수 있다.

answer = []
max_v = 0
for i in range(1, n+1):
    tmp_v = bfs(i)

    if max_v < tmp_v:   # 해킹할 수 있는 컴퓨터 수가 더 많은 경우
        answer = [i]    # 배열 초기화
        max_v = tmp_v   # 업데이트
    elif max_v == tmp_v:    # 수가 같은 경우에는 추가
        answer.append(i)

print(*answer)