cycle

백준 2623번: 음악프로그램 (파이썬, 위상정렬, Cycle)

유향그래프를 정렬하는 문제이고 사이클이 없으므로 위상정렬을 이용하여 풀었다. 앞서 푼 '2252번: 줄세우기' 문제와 사이클이 존재할 때와 존재 안할 때를 판별하는 것이 차이점이 였다. 위상 정렬을 하기 위해서는 사이클이 없어야 하므로 문제의 조건을 하나 추가한 것 같다. 위상정렬은 DFS로 그래프를 정렬 후 뒤짚는 방식으로 구현하였다. 사이클 판별은 두가지로 해보았다. 첫번째 방법은 노드 수 N과 크기가 같은 boolean 배열을 하나 만들어서 V의 종단노드부터 boolean 배열의 원소 값을 True로 한다. 그 후 종단노드의 부모노드 순으로 boolean 배열의 원소 값을 True로 한다. 이때 부모노드의 boolean 배열의 원소값이 False라면 Cycle이 존재한다고 판별하는 방법이다. 왜냐하..