[임계 경로 알고리즘] Critical Path Method (백준-1948 해설)

문제

 

https://www.acmicpc.net/problem/1948

1948번: 임계경로

 

 

풀이

 

solved.ac 난이도: Platium 5

 

위상 정렬(Topological Sort)을 이용하여 임계 경로(Critical Path)를 구현하는 문제였다.

 

임계 경로(Critical Path)

임계 경로는 프로젝트 완성에 필요한 시간을 계산하는 스케줄 관리 도구로 자주 사용된다.

프로젝트는 각각의 작업으로 세분화되고 작업들은 특정 작업이 선수되어야만 하는 의존성(선후 관계)을 가진다.

이러한 선후 관계들을 Directed Graph로 연결하면 DAG(Directed Acycle Graph), 사이클이 없는 그래프로 표현이 된다.

DAG의 선후 관계들로 정렬을 진행하는 것이 바로 위상 정렬이므로 임계 경로를 구현하는데 알맞은 알고리즘이다.

프로젝트의 DAG로 위상 정렬을 진행하면 각 작업이 어떠한 순서로 진행이 되어야 하는지  알 수 있다.

 

특히 각 작업에서 다음 작업으로의 소요 시간을 그래프로 표현하여 해당 작업에 얼마나 많은 시간이 필요한지, 프로젝트의 전체 소요시간이 얼마나 걸리는지 확인할 수 있다.

 

 

이번 문제로 돌아와서,

도시에서 도로 몇 시간 동안 타고 다른 도시로 이동하는 것을 , 한 작업을 몇 시간 안에 끝내 다음 작업을 준비하는 것으로 바꾸면 프로젝트의 임계 경로를 구하는 문제와 다를 것 없다.

 

우리는 두가지 질문에 답을 해야 한다.

 

1. 시작 도시에서 출발하여 도착 도시로 모두가 도착하는데 걸리는 최소 시간

이는 프로젝트의 시작에서 모든 작업이 마무리되어 프로젝트에 도달하는 소요시간을 구하는 것과 동일하다.

 

임계 경로에서 작업 간의 선후 관계, 즉 의존도는 해당 작업을 하기 위해 미리 선수되어야 하는 작업들을 의미한다.

따라서 해당 작업의 선수 작업들이 모두 완료되어야 해당 작업을 진행할 수 있기에 선수 작업들 중 가장 긴 소요 시간이 해당 작업을 시작할 수 있는 시간이다.

 

 

이번 문제로 이를 바꾸어 표현하면 해당 도시로 들어오는 모든 도로들 중 가장 소요 시간이 큰 것이 해당 도시에서 출발할 수 있는 시간이다.

따라서 해당 도시로 도달하는데 걸리는 가장 큰 소요 시간을 해당 도시에서 출발하는 시간으로 저장하자.

 

이를 가장 구현하기 편리한 것이 큐를 이용한 위상 정렬을 구현하는 것이다.

해당 도시(city_idx)로 진입하는 도로의 수를 indegree[city_idx]에 저장하여

indegree[city_idx] =0 인, 출발 도시에서부터 연결된 도로로 도시들을 이동한 후 도로를 끊어주자.

=> 도로가 끊기면 진입 간선이 끊긴 것이므로 --indegree[city_idx]로 표현한다.

 

새로 생긴 indegree[city_idx] =0인 도시들, 선수 방문 도시(=선수 작업)를 모두 방문한 도시들에서 다시

이동 가능한 도로의 연결도 끊어주는 작업을 반복한다.

이때 선수 도시들은 이미 자신들의 선수 도시의 방문이 끝났으므로 자신에게 도달하는 가장 큰 소요 시간도 이미 알 수 있다.

따라서 선수 도시들에서 해당 도시(city_idx)로의 이동 소요시간 중 가장 큰 시간을

max_arrival_time[city_idx]에 저장하자.

max_arrival_time[city_idx] = max(max_arrival_time[city_idx] ,max_arrival_time[선수 도시] + time_cost );

 

 

최종적으로 모든 도시를 방문했다면 가장 마지막에 방문되었을 도착 도시(dest_city)의 max_arrival_time[dest_city]이 1번 질문의 답이 된다.

 

 

int start_city, dest_city;
cin>>start_city>>dest_city;
queue<int> que; //큐에 들어가는 도시는 간선이 모두 제거되어 도착 최대 시간을 저장하고 있는 경우
que.push(start_city);
  
int now_city_idx;
for(int idx=0; idx<city_num ; ++idx){
  now_city_idx = que.front();
  que.pop();
 
  for(int i=0; i<adj_time[now_city_idx].size() ; ++i){
    dest_idx = adj_time[now_city_idx][i].first;
    time_cost = adj_time[now_city_idx][i].second;
 
    --indegree[dest_idx];
    max_arrival_time[dest_idx] = max(max_arrival_time[dest_idx] ,max_arrival_time[now_city_idx] + time_cost );
 
    if(indegree[dest_idx]==0)
      que.push(dest_idx);
  }
}

 

 

 

2. 쉬지 않고 달려야 하는 도로의 개수

 

이것을 구하기 위해 1번에서 각 도시의 최대 도착 시간을 저장해 준 것이다.

만약 이 질문에 답할 필요가 없었다면 단순한 DFS나 BFS 알고리즘으로도 도착 도시로의 최대 cost 경로는 간단히 구할 수 있었을 것이다.

 

쉬지 않고 달려야 하는 도로는 해당 도로가 최대 시간 경로에 포함되어 있기 때문에 쉬엄쉬엄 지나갈 수 없음을 의미한다.

따라서 시작 도시에서 도착 도시로의 최대 소모 시간 경로에 있는 모든 도로의 수(간선의 수)를 세어주자.

이를 찾기 위해 저장해둔 max_arrival_time를 이용하자.

 

이번에는 그래프를 도착 도시에서 출발해 출발 도시로 도착하도록 역방향으로 진행한다.

 

만약 해당 도시에서 도로로 연결된 선수 도시로의 소요 시간(time_cost)이

max_arrival_time[해당 도시] - max_arrival_time[선수 도시]가 아니라면 이 도로는 최대 소모 시간 경로에 포함되자 않는 경우이다.

만약 최대 경로에 포함되었다면 max_arrival_time[선수 도시]+ time_cost  = max_arrival_time[해당 도시]로

해당 도시의 최대 도착 시간으로 계산 되었을 것이다.

 

 

따라서 역순으로 진행하며 위 조건을 만족하는 경우만 큐에 넣어 세어주자.

조건을 만족하지 않는 다면 해당 선수 도시로의 경로들은 전혀 의미가 없으므로 큐에 삽입하지 않는다.

단, 중복된 도로를 세주지 않기 위해 방문한 도시는 visited표시를 하여 재 방문하지 않도록 구현하였다.

 

  queue<int> re_que;  //역 방향으로 진행
  re_que.push(dest_city);
  
  int road_cnt=0;
  while(1){
    now_city_idx = re_que.front();
    re_que.pop();
 
    if(now_city_idx == start_city)
      break;
 
    for(int i=0; i<reverse_adj[now_city_idx].size() ; ++i){
      dest_idx = reverse_adj[now_city_idx][i].first;
      time_cost = reverse_adj[now_city_idx][i].second;
 
      if(max_arrival_time[now_city_idx] - max_arrival_time[dest_idx] ==time_cost){
        ++road_cnt;
        if(!visited[dest_idx]){
          visited[dest_idx] = true;
          re_que.push(dest_idx);
        }
      }
 
    }

 

참조 게시글

얍문님의 1948문제 해설

푸른하늘의해님의 CPM 네트워크

코드