[SWEA 1267] 작업순서 C++

 

SW Expert Academy

 

 

문제풀이

 

해야 할 V개의 작업이 있는데 어떤 작업은 특정 작업이 끝나야 시작할 수 있다.

이를 선행 관계라 한다.

이런 작업의 선행 관계를 나타낸 그래프가 주어졌을 때, 한 사람이 한 번에 하나씩 일할 수 있는 작업 순서를 찾는 문제다.

 

 

 

 

위상 정렬을 사용하여 문제를 해결했다.

선행 관계를 입력받아서 그래프를 만들어주고 cnt 배열에 각 정점이 가지는 선행 정점의 수를 저장한다.

 

 

작업 순서를 찾기 위해 먼저 cnt[i]가 0인 정점들을 큐에 넣어준다.

cnt[i] = 0은 선행 정점이 없으므로 바로 작업을 처리할 수 있다.

 

큐에서 정점을 하나씩 꺼내면서 정점을 출력하고 해당 정점과 연결된 정점들의 선행 정점 개수를 1 감소시킨다.

선행 정점이 0개인 경우에는 큐에 넣고 계속 반복하면 작업 순설를 찾을 수 있다.

 

 

C++ 코드