(전공복습) 데이터과학 4. 시각화
차례
위상 정렬(Topological Sort)을 활용하면 쉽게 풀 수 있는 문제.
처음엔 꽤 오래 고민했는데, 위상 정렬이 사이클을 탐지할 수 있다는 점을 생각하면 쉽게 풀 수 있다.
전체 학생들에 대해 위상정렬을 했을 때, 사이클은 진입차수가 1이 될 것이고,
따라서 위상정렬이 가능한 학생의 수가 사이클에 속하지 않은 학생의 수, 다시 말해 팀에 속하지 못하는 학생의 수가 될 것이다.
여기까지 떠올렸다면 그냥 위상정렬을 하는 것만으로도 문제는 풀린다.
from sys import stdin
from collections import deque
input = stdin.readline
t = int(input())
for _ in range(t):
n = int(input())
arr = [0] + list(map(int, input().split()))
# 진입차수 리스트
idg = [0] * (n+1)
graph = [[] for _ in range(n+1)]
# 그래프 및 진입차수 갱신
for i, e in enumerate(arr):
graph[i].append(e)
idg[e] += 1
# 진입차수가 0인 노드들을 넣음
q = deque()
for i, e in enumerate(idg):
if not e:
q.append(i)
# 위상정렬 수행
ans = 0
while q:
node = q.popleft()
# 위상정렬이 된 노드들의 개수가 답이 됨
ans += 1
for e in graph[node]:
idg[e] -= 1
if not idg[e]:
q.append(e)
print(ans)
문제 링크 문제 링크
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...