[백준 1352] (bfs)효율적인 해킹 - python

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

1325번: 효율적인 해킹

 

문제풀이

DFS - 런타임에러

• 처음에 DFS로 풀이를 했는데 N, M값이 큰 탓인지 런타임에러가 발생했다 ㅠㅠ
• DFS는 O(N^2)의 시간복잡도를 가져 그런 것 같다,, 다른언어로 푸신 분들은 통과했던데 how,,,
• 일단 DFS풀이를 살펴보면, 이 문제에서 포인트는 a가 b를 신뢰하면 b가 해킹당했을 때 a도 해킹당한다는 것이다
• 즉, b -> a인 단방향 그래프로 만들어줘야했다
• 그리고 해킹 당하는 컴퓨터를 한 번 한 번 확인해야하기 때문에 for문 안에서 dfs함수를 실행했다 (i가 계속 바뀌도록)
• 그 외엔 일반적인 DFS방법으로 풀이했다
• 그리고 result를 컴프리헨션 방식으로 value가 max_value값과 같은 값들만 list에 담아내도록 했다
• Asterisk(*)를 사용하여 result에 있는 값을 풀어냈다

def dfs(computers, v, count, visited, point):
    visited[v] = 1
    count[point] += 1
    for i in computers[v]:
        if visited[i] == 0:
            # print(i, end=' ')
            dfs(computers, i, count, visited, point)



n, m = map(int, input().split())
computers = [[] for _ in range(n+1)]
count = [0] * (n+1)

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


for i in range(1, n+1): # 1부터 시작
    point = i
    visited = [0] * (n+1)
    dfs(computers, i, count, visited, point)
# print(count)

max_value = max(count)
result = [x for x, value in enumerate(count) if value == max_value]
print(*sorted(result))

 

BFS

• DFS함수를 BFS바꾼 것 외엔 나머지 코드는 DFS코드와 동일하다
• bfs를 사용하여 문제를 통과했다,,!
• 아무래도 DFS에서 재귀가 너무 깊이 들어간게 아닐까 예측한다

from collections import deque
def bfs(computers, v, count, visited, point):
    queue = deque([v])
    count[point] += 1
    visited[v] = 1
    while queue:
        i = queue.popleft()
        for com in computers[i]:
            if visited[com] == 0:
                # print(com)
                queue.append(com)
                count[point] += 1
                visited[com] = 1

n, m = map(int, input().split())
computers = [[] for _ in range(n+1)]
count = [0] * (n+1)

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

# print(computers)

for i in range(1, n+1): # 1부터 시작
    point = i
    visited = [0] * (n+1)
    bfs(computers, i, count, visited, point)
# print(count)

max_value = max(count)
result = [x for x, value in enumerate(count) if value == max_value]
print(*sorted(result))