백준 1167 (1) 썸네일형 리스트형 임계경로(Critical Path) 알고리즘 임계경로(Critical Path) ! 본 글에서는 임계경로의 지나온 경로는 구하지 않고 임계경로의 길이만 구한다 ! 그래프에서 임계경로란 어떤 시작지점으로부터 끝지점까지의 최장경로를 의미한다. 보통 그래프에서 경로의 길이를 구하면 최소경로를 찾는 것이 대부분이었을 것이다. 최장거리를 구한다는 것은 무슨 의미가 있을까? 다음과 같은 그래프가 있다고 가정하자. 위 그래프는 앞서 위상정렬(링크)에서 사용했던 그래프이다. 각 노드를 일이라고 표현해보자. 또한 빨간색 숫자는 각일을 할때 걸리는 시간이다. 해당 노드의 일을 끝내야 다음노드의 일을 끝낼 수 있다. 그렇다면 모든 일이 종료될때 까지의 최소시간은 무엇일까? 아무리 빠른 경로로 가서 마지막일을 끝내봤자 다른일이 끝나지 않았다면 의미가 없을 것이다. 이때.. 이전 1 다음
