📜문제 설명
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
📍입력
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
5 4
3 1
3 2
4 3
5 3📍출력
첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.
1 2📄문제 해결
📝내가 푼 코드
❎ 1차 시도
def dfs(graph, node, visited):
if node in visited:
return 0
visited.add(node)
count = 1 # 자기 자신 포함
for neighbor in graph[node]:
count += dfs(graph, neighbor, visited) # 탐색한 노드 수 추가
return count
N, M = map(int, input().split(' '))
graph = {n:[] for n in range(1, N+1)} # 컴퓨터는 1번부터 N번까지 존재
for _ in range(M):
a, b = map(int, input().split(' '))
graph[b].append(a) # a가 b를 신뢰, b에서 a에 접근 가능
# 해킹 가능한 컴퓨터 개수 카운트
cnt = [[n, 0] for n in range(1, N+1)]
for n in range(1, N+1):
visited = set() # 방문한 노드를 저장할 집합
cnt = dfs(graph, n, visited) # 1번 노드에서 시작
cnt[n-1][1] = cnt
cnt.sort(key=lambda x: x[1], reverse=True) # 해킹할 컴퓨터가 많은 순으로 정렬
m = cnt[0][1]
for k, v in cnt:
if m > v: break
print(k, end=' ')문제를 읽고 분석하면서 이는 그래프 탐색 알고리즘을 활용해야 한다는 확신이 들었다.
5는 4를 신뢰하면 4를 해킹 시에 5도 해킹이 가능하기에 4->5와 같이 방향이 있는 그래프로 이를 연결할 수 있는 것이었다. 문제의 예제도 분석해보면 1, 2를 해킹하면 3을 해킹할 수 있고, 3으로 4, 5를 해킹할 수 있어 1, 2 컴퓨터가 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 경우가 된다. (1, 2->3->4, 5)
직관적으로 쉽게 풀기 위해서는 DFS가 더욱 적절하다는 생각이 들어 DFS 알고리즘을 선택했고, 탐색하며 방문한 노드의 개수를 세서 저장한 뒤, 내림차순 정렬하여 가장 높은 값만 가진 노드(컴퓨터)만 출력할 수 있도록 했다. 예제처럼 두 가지 이상의 컴퓨터인 경우를 고려하였다.
코드만 보면 크게 문제가 있어 보이지는 않았다. 하지만 백준에서 할당한 메모리와 시간 제한으로는 파이썬으로 이 문제를 풀 수가 없었다...😂 멘토님께서도 상대적으로 다른 언어보다 느려 최적화가 어려운 파이썬으로는 쉽지 않은 문제였다고 말씀하셨던 것처럼, 나는 시간 초과라는 결과를 얻었다.
🤔느낀점
오늘 문제를 분석하면서 자연스럽게 그래프 탐색 알고리즘을 활용해야 한다는 것을 알아차린 스스로가 아주 뿌듯했다!
