[solved.ac 실버1] 1325_효율적인 해킹 (파이썬, BFS)

제한 사항

 

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

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

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

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

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

예제

---

나의 풀이

이러한 탐색 문제는 DFS와 BFS 둘 다 가능한 유형이다. 이 문제에서는 인접 리스트를 어떻게 만드느냐가 관건이 되겠다.

 

전역 변수

from collections import deque
import sys

input = sys.stdin.readline

answer = []
max_hacked = 0

BFS를 이용해 풀이할 것이므로 deque을 import 했고, 최대 100,000 개의 신뢰 관계를 입력 받아야 해서 sys.stdin.readline을 사용했다.

answer에는 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호들이 저장될 것이고, max_hacked는 가장 많이 해킹 당한 횟수가 저장된다.

 

사용자 입력

# user_input
n, m = map(int, input().split())
arr = [list() for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    arr[b].append(a)

n과 m을 입력 받고 arr에 n + 1 크기의 리스트를 만든다. (인덱스를 1부터 시작하기 위해서)

그리고 m개의 신뢰 관계 a, b를 입력 받는데 문제를 다시 한 번 잘 봐야 한다.

A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다.

 

이 문제는 해킹할 수 있는 컴퓨터의 수를 구해야하므로 arr의 i번째 인덱스에는 i번 컴퓨터를 해킹했을 때 같이 해킹할 수 있는 컴퓨터의 목록이 저장되어야 한다.

즉, arr[b].append(a)와 같이 저장해야 한다는 말이다.

 

BFS

def bfs(start):
    avail = 0
    visited = [False] * (n + 1)
    visited[start] = True
    queue = deque([start])

    while queue:
        now = queue.popleft()
        for computer in arr[now]:
            if visited[computer]: continue
            visited[computer] = True
            avail += 1
            queue.append(computer)

    return avail

bfs 함수를 돌 때면 해킹 가능한 수를 체크하기 위한 avail 변수를 0으로 초기화 하고, visited 리스트로 만든다.

현재 컴퓨터가 now라고 했을 때 now를 해킹하면 같이 해킹할 수 있는 컴퓨터들이 arr[now]에 저장되어 있다.

이 목록을 순회하면서 아직 해킹(방문)하지 않은 컴퓨터라면 방문처리를 하고 avail을 1 증가시키면서 큐에 넣는다.

함수가 끝나면 avail에는 해킹 가능한 컴퓨터의 수가 저장되어 있을 것이다.

 

로직

def solution():
    global max_hacked, answer

    for i in range(1, n + 1):
        hacked = bfs(i) # 해킹 가능한 컴퓨터 수

        if hacked > max_hacked:
            max_hacked = hacked
            answer = [i]
        elif hacked == max_hacked:
            answer.append(i)

    # 정답 출력
    for com in answer:
        print(com, end=' ')

1번 컴퓨터부터 n번 컴퓨터까지의 해킹 가능한 컴퓨터의 수를 확인하는 부분이다.

만약 i 번 째 컴퓨터의 해킹 가능한 컴퓨터 수가 지금까지의 최대 해킹 수보다 크다면 그 수를 갱신하고, answer에 i 컴퓨터만을 저장한다.

만약 i 번 째 컴퓨터의 해킹 가능한 컴퓨터 수가 지금까지의 최대 해킹 수와 같다면 answer에 i 컴퓨터를 추가한다.

 

1번 컴퓨터부터 n번 컴퓨터까지 오름차순으로 탐색했기 때문에 자연스럽게 answer에는 오름차순으로 값이 들어가 있을 것이다. 바로 출력해주면 답이 된다.

 

채점 결과