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

문제 링크 >> https://www.acmicpc.net/problem/1325 

 

 

📋 문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다.

이 회사는 N개의 컴퓨터로 이루어져 있다.

김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

 

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

 

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에, N과 M이 들어온다.

N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다.

둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다.

컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

 

 

👈출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

 

📝 풀이

import sys
from collections import deque

def bfs(graph, v):
  q = deque([v])
  visited = [False]*(n+1)
  visited[v] = True
  count = 1
  
  while q:
    temp_v = q.popleft()
    for i in graph[temp_v]:
      if not visited[i]:
        q.append(i)
        visited[i] = True
        count += 1

  return count

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

for _ in range(m):
  v1, v2 = map(int, sys.stdin.readline().split())
  graph[v2].append(v1)

answer = []
for i in range(1, n+1):
  answer.append(bfs(graph, i))

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

 

그래프의 간선이 방향이 있는 간선이라 좀 까다로웠던 문제였다.

방향성이 있는 건 처음 풀어봤는데 이 경우에는 방문했던 노드를 다시 방문하는 경우도 생각해야 하기 때문에 visited의 선언부를 bfs 안으로 이동하면 된다.

 

처음에는 dfs로 연결되어 있는 컴퓨터들을 파고들어 가려고 했는데 영 감이 잡히지 않아 bfs로 풀었더니 원하는 결과가 바로 나왔다.

dfs나 bfs나 좀 더 많은 문제를 풀어봐야할 것 같다.

 

참고로 이 문제는 Python3로 제출하면 시간 초과가 나니 PyPy3로 제출하면 마음이 편하다.