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

 실버1~2 문제를 손풀기 겸 뇌 깨우기로 계속해서 풀고 있다. 한창 백준 티어 끌어올리기 할 때 만큼 빠르지는 않지만 문제 해석 능력과 자료구조, 알고리즘 적용 감각이 돌아오고 있는 것이 느껴저 좋다. 이번 문제는 간단하게 그래프를 사용하여 풀 수 있는 문제이다.

문제

 

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

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

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

입력

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

출력

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

예제 입력 1

5 4
3 1
3 2
4 3
5 3

예제 출력 1

1 2

 

정답 코드

N, M = map(int, input().split())

graph = [set() for _ in range(N)]

for _ in range(M):
    A, B = map(int, input().split())    
    graph[B-1].add(A-1)

result = []
maxCount = 0

for start in range(N):
    
    q = [start]
    qlen = 1

    visited = [False] * N
    visited[start] = True

    while q:
        com = q.pop()
        
        for c in graph[com]:
            if not visited[c]:
                visited[c] = True
                q.append(c)

    if maxCount < visited.count(True):
        result = [start + 1]
        maxCount = visited.count(True)
    elif maxCount == visited.count(True):
        result.append(start + 1)

print(*result)

 

 문제와 같이 그래프를 구성한다. 주의할 점은 A, B 순서대로 입력하지만 신뢰하는 관계는 반대로 적용된다. A가 B를 신뢰하면 B를 해킹할 때 A도 동시에 해킹할 수 있으므로 그래프 상에서는 B->A 방향으로 연결한 방향그래프로 이루어져야 한다. 그래프 구성이 완료되면, 각 시작점을 1부터 N까지로 하는 각각의 그래프 탐색을 시행하여 방문한 개수를 세고, 최대 개수가 되는 시작점들을 모아 출력한다.