✓

태그:

34. 위상 정렬 CLASS 5 ESSENTIAL

위상… 정렬…??

풀이 비스무리한거 보기

어떤 건물을 짓기 위한 선행 건물 건설 조건이 주어질 때, 목표한 건물을 짓는 데에 걸리는 최소 시간을 구하는 문제입니다. 위상 정렬이라는 것을 사용하는 모양입니다. 위상 정렬은 주어진 단방향 그래프에서 자신에게 향하는 간선이 없는 노드를 큐에 집어넣고 간선을 하나씩 제거하면서 자신을 향하는 간선이 없는 노드를 찾아 계속 큐에 추가하는 방법입니다. 간단히 설명하면 아래와 같습니다.

1. 주어진 그래프에서 자신을 향하는 간선이 없는 노드를 큐에 모두 추가
2. 큐의 각 원소에 대해
   1. 노드에서 다른 노드로 향하는 간선 제거
   2. 해당 다른 노드로 향하는 간선의 개수가 0이 되면 큐에 추가

이 방법으로 노드를 순회하되, 이전 건물까지 짓는 데에 걸리는 최소 시간(또는 이전 노드까지 탐색하는 데에 걸리는 최소 시간)을 저장해가면서 노드를 순회하면 목표로 하는 건물을 짓는 데에 걸리는 최소 시간을 구할 수 있습니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-03-01 22:20:23

---