해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 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 = ' ')