[Python] 1325번 효율적인 해킹

✏️ 문제

 

문제 파악

시간 제한이 5초로 시간 초과가 뜨지 않도록 하는 게 이 문제의 핵심이다.. 메모리도.. (둘 다 초과 떠본 사람이) 

아마 이 두 개의 제한이 정답 비율을 낮게 만든 요인일 듯.. 

 

인접리스트랑 BFS를 활용해서 풀었는데 각 컴퓨터의 해킹할 수 있는 컴퓨터의 개수를 저장해야 하므로 컴퓨터 하나하나를 BFS를 돌아야 한다. 그래서 각각의 컴퓨터가 BFS 돌 때 방문 처리를 해줘야 하므로 방문 배열을 BFS 함수 내에서 초기화해야 한다.

 

python으로 풀고 싶어서 오래 붙잡아봤지만 결국 못풀었다 ㅠ pypy3로 제출하니까 되긴 됐는데 다른 분들의 많은 코드를 봤지만 대부분 pypy3로 푸는 듯.. python으로 푼 사람이 있을까.. !! 궁금하다 그 코드!

 

알고리즘

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

 

 

코드

• 메모리 초과 코드

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

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

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

def bfs(x):
  q = deque([x])

  while q:
    node = q.popleft()

    for neighbor in graph[node]:
      computer[x] += 1
      q.append(neighbor)

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

for i in range(1, n+1):
  if computer[i] == max(computer):
    print(i, end=' ')

graph와 computer 배열 때문에 메모리 초과가 뜨나 싶어서 딕셔너리로도 변경해봤으나 똑같이 메모리 초과가 떴다 ㅠ..

• pypy3 로 제출해서 성공한 코드

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

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

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

def bfs(x):
  q = deque([x])
  cnt = 0

  visited = [0] * (n+1)
  visited[x] = 1

  while q:
    node = q.popleft()

    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = 1
        q.append(neighbor)
        cnt += 1

  return cnt

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

for i in range(len(computer)):
  if computer[i] == max(computer):
    print(i+1, end=' ')

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS