[Python][백준/BOJ] 1325번 : 효율적인 해킹

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

1325번: 효율적인 해킹

 

내 코드

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

n, m = map(int, input().split())
graph =[[] for _ in range(n+1)]
depth =[1 for _ in range(n+1)]
ans = []*(n+1)
res =[]
for _ in range(m):
    a, b = map(int, input().split())
    graph[b].append(a)

def bfs(x):
    visited = [0]*(n+1)
    visited[x] =1
    q= deque()
    q.append(x)
    cnt =1
    while q:
        i = q.popleft()
        for j in graph[i]:
            if not visited[j]:
                cnt+=1
                visited[j] =1
                q.append(j)
    return cnt
                
            
for i in range(1,n+1):
    ans.append(bfs(i))
    
for k in range(n):
    if max(ans) == ans[k]:
        res.append(k+1)
print(' '.join(map(str,res)))

 

코드 리뷰, BFS

해당 문제를 보자마자 DFS로 접근했다. 각 컴퓨터가 연결되어 있을 때 가장 많이 연결된 컴퓨터를 찾는 문제이기 때문이다.

그래서 깊이를 재고, 이를 출력하면 될 줄 알았다. 하지만 DFS로 풀자 시간 초과가 발생했다. 

컴퓨터의 개수는 총 10,000까지 가능하고, DFS로 접근한다면 10,000개의 가중치를 5초 안에 계산해야 하기 때문이다.

그래서 BFS로 다시 접근했다.

BFS로 접근한다면 방문하지 않은 컴퓨터만을 방문해가며 연결된 컴퓨터의 개수를 계산해주는 것이다.

 

이 문제에서 주의해야 할 부분이 하나 있는데, 바로 graph 초기화이다.

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

문제의 일부인데, 이 말에 의하면 A B로 입력되어 있을 때 B가 해킹되면 A가 해킹되는 것이므로 graph[b].append(a)가 된다. 

그리고 visited 배열로 방문 기록을 하지 않는다면 메모리 초과 오류도 발생한다고 하니 주의하자.

 

또 내가 느낀바로는 bfs문제와 dfs 문제가 다른 점이 for문을 하나 더 생성해주어야 한다는 점에 있다.

for i in range(1, n+1):
	bfs(i)

dfs는 숫자 하나만 달랑 전달해주면, 연결된 부분을 타고 알아서 훑기 때문에 상관이 없다. 하지만 bfs같은 경우에는 넓게 훑어야 하기 때문에 훑어야 하는 전체 부분에 대해 for문을 돌려주어야 한다는 점이 다른 것 같다.