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

문제

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

1325번: 효율적인 해킹

코드

import sys
from collections import deque


def bfs(start):
    q = deque([start])
    visited = [False] * (n + 1)  # 방문 여부 기록
    visited[start] = True  # 해킹 시작 노드는 방문 체크
    hacking_cnt = 1  # 해킹 횟수
    while q:
        com = q.popleft()
        for i in graph[com]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                hacking_cnt += 1
    return hacking_cnt


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

answer = []  # 한번에 가장 많은 해킹을 할 수 있는 컴퓨터 번호들을 저장
max_cnt = 1  # 가장 많이 해킹할 때 해킹 수
for i in range(1, n + 1):
    cnt = bfs(i)
    if max_cnt < cnt:
        answer = [i]  # 초기화
        max_cnt = cnt  # 해킹 수 초기화
    elif max_cnt == cnt:
        answer.append(i)
answer.sort()
print(' '.join(map(str, answer)))

풀이

(n + 1) 의 행을 가진 2차원 배열 graph를 선언합니다.

m 만큼 반복문을 돌면서 A, B를 입력받고 graph[B]에 A를 append합니다.

A가 B를 신뢰하기 때문에 B가 해킹당하면 연쇄적으로 A도 해킹당하게 됩니다.

 

BFS를 이용하여 시작 노드를 매개변수로 해킹 횟수를 구하는 함수를 선언합니다.

 

한번에 가장 많은 해킹을 할 수 있는 시작 노드를 저장하는 리스트 answer와

가장 많이 해킹할 때 해킹 수를 저장하는 max_cnt를 선언합니다.

bfs를 호출하여 나온 결과값을 cnt라고 할 때,

cnt가 max_cnt보다 크면, 새로운 최대 최대 해킹수가 나왔다는 뜻이므로 answer와 max_cnt를 초기화 합니다.

cnt가 max_cnt와 같으면, 최대 해킹수 같은 노드가 나왔다는 뜻이므로 answer에 노드를 추가합니다.

최종적으로, answer의 값을 출력하면 답이 됩니다.