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

문제

백준 1325번 - 효율적인 해킹

해결 과정

• BFS로 풀었다.
  A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
• 기본 BFS 구현과 비슷하다 반드시 암기!
• graph에 값을 한 방향으로만 넣는다.
• BFS가 return하는 cnt값이 가장 큰 값이면 result에 넣고 안에 있던 값은 지우고 max_num을 해당 값으로 업뎃
  • elif 가장 큰 값과 같으면 result에 넣는다

시행착오

• dfs 풀이 틀렸다. 왜?

import sys
n,m = map(int,sys.stdin.readline().split())
graph = [[] for i in range(n+1)]

def dfs(v):
  global cnt
  cnt += 1
  for i in graph[v]:
    dfs(i)
    break

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

result = []
max_num = 0
for i in range(1,n+1):
  cnt = 0  
  dfs(i)
  if max_num <= cnt:
    result.append(i)
    max_num = cnt

print(*result)

• bfs풀이 시간초과 왜?
  • 함수의 return으로 cnt 반환하기
  • visited 배열도 함수 안에서 정의하기
    함수 사용할 때마다 새로운 배열로 사용되니까

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
graph = [[] for i in range(n+1)]


for i in range(m):
  a,b = map(int,sys.stdin.readline().split())
  graph[b].append(a)
  
cnt = 0
def bfs(start):
  global cnt
  q = deque([start])
  visited[start] = True
  
  while q:
    v = q.popleft()
    cnt += 1
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True

result = []
max_num = 0
for i in range(1,n+1):
  cnt = 0  
  visited = [False] * (n+1)
  bfs(i)
  if max_num <= cnt:
    result.append(i)
    max_num = cnt

print(*result)

풀이

import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())

def bfs(start):
  cnt = 1
  visited = [False] * (n+1)
  q = deque([start])
  visited[start] = True
  while q:
    v = q.popleft()
    for i in graph[v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True
        cnt += 1
  return cnt
  
graph = [[] for i in range(n+1)]
for _ in range(m):
  a,b = map(int,sys.stdin.readline().split())
  graph[b].append(a)  
  
result = []
max_num = 1
for i in range(1,n+1):
  cnt = bfs(i) 
  if max_num < cnt:
    max_num = cnt
    result.clear()
    result.append(i)
  elif max_num == cnt:
    result.append(i)
print(*result)