유자의 코딩모험

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 해야 할 V개의 작업이 있는데 어떤 작업은 특정 작업이 끝나야 시작할 수 있다. 이를 선행 관계라 한다. 이런 작업의 선행 관계를 나타낸 그래프가 주어졌을 때, 한 사람이 한 번에 하나씩 일할 수 있는 작업 순서를 찾는 문제다. 위상 정렬을 사용하여 문제를 해결했다. 선행 관계를 입력받아서 그래프를 만들어주고 cnt 배열에 각 정점이 가지는 선행 정점의 수를 저장한다. 작업 순서를 찾기 위해 먼저 cnt[i]가 0인 정점들을 큐에 넣어준다. cnt[i] = 0은 선행 정점이 없으므로 바로 작업을 처리할 수 있다. 큐에서 정점을 하나씩 꺼내면서 정점을 출력..

플로이드 와샬 알고리즘이란? '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 다익스트라 알고리즘과의 차이점 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘으로 가장 적은 비용을 하나씩 선택한다. 하지만 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 모든 정점'을 기준으로 알고리즘을 수행한다. 알고리즘 위와 같은 그래프가 존재한다고 할 때, D는 각각의 정점이 다른 정점으로 가는 비용을 이차원 형태로 저장해놓은 것이다. 처음에는 위와 같은 상태이다. 이때 무한대는 이동하는 경로가 없다는 뜻이고 자신 자신의 비용은 0이다. D[x][y] = x에서 y로 가는 최소 비용을 의미한다. 거쳐가는 정점을 K라고 하자. X에서 Y로 가는 최소 비용과 X에서 노드 K로 ..