오늘의 알고리즘 - boj-1325

문제

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

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

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

풀이

B를 해킹하면 A도 해킹할 수 있다는 말을 통해서 단방향 그래프를 생각해내야 풀 수 있는 문제라고 생각한다.

무방향 그래프라면 양 방향에 대해서 그래프를 만들어줘야 하지만 A를 해킹하면 B도 해킹할 수 있다는 말이 없는 이상 한 방향으로만 조건이 적용된다는 사실을 알 수 있다.

그래프를 선언해주고나면 그 아래에 최대 몇개의 노드를 가지는지 구하기만하면 풀 수 있는데 나는 bfs로 값을 계산했고 방문하지 않은 노드들을 하나씩 담으면서 담을 때 마다 cnt를 하나씩 증가시킨 다음 cnt값을 반환해줬다.

마지막으로 for루프를 순회하면서 각 노드별 해킹이 가능한 컴퓨터의 갯수를 반환하고 그 값들 중 max값을 구해준다.

max값을 구하고나면 그 max값과 일치하는 값을 프린트해준다. (이 전에 for 루프를 돌면서 순서대로 answers에 값을 넣었기 때문에 이미 정렬되어있다.)

from collections import deque, defaultdict
import sys
input = sys.stdin.readline
    

def get_possible_hacking_count(start):
    visited = [0] * (N+1)
    queue = deque([start])
    visited[start] = 1
    cnt = 1
    while queue:
        cur_node = queue.popleft()
        for next_node in graph[cur_node]:
            if visited[next_node] == 0:
                queue.append(next_node)
                visited[next_node] = 1
                cnt+=1
    return cnt

if __name__ == '__main__':
    N, M = map(int, input().rstrip().split())
    graph = defaultdict(list)
	
    for _ in range(M):
        node1, node2 = map(int, input().rstrip().split())
        
        graph[node2].append(node1)
    
    answers = []
    max_cnt = 0
    for i in range(1, N+1):
        possible_hacking_count = get_possible_hacking_count(i)
        max_cnt = max(max_cnt, possible_hacking_count)
        answers.append((possible_hacking_count, i))
	    
    for possible_hacking_count, idx in answers:
	    if possible_hacking_count == max_cnt:
	        print(idx, end = ' ')