시간초과가 나오는 이유를 잘 모르겠습니다.. for문 같은 것을 많이 줄이고 쓸데 없는 부분을 많이 줄였는데 그래도 시간초과가 나오네요ㅠㅠ

혹시 시간복잡도에 대해 잘 아시는 분이 계시다면 한번만 봐주시면 감사하겠습니다. 너무 풀어보고 싶은데 답답하네요 ㅠㅠ

dfs를 돌면서 이미 visit된 정점을 만났을 때 그 정점을 V라고 하면,

정점 V가 현재 실행된 dfs에 의해 방문된 노드인지(상황 1) 아니면 이전에 돌린 dfs에 의해 방문된 노드인지(상황 2) 판단할 수 있습니다.

(상황 1)이라면 사이클을 찾은것이고, (상황 2)라면 사이클을 찾지 못한 경우입니다.

(상황 2)가 사이클을 찾지 못한 경우가 되는 이유는 각 정점은 단 하나의 간선만을 가지기때문입니다.

현재 코드를 보면 check를 dfs가 끝난 후에 int 1 또는 2로 하고있는데,

dfs 안에서 check를 해나가면서, 동시에 check[v]에 들어가는 값을 잘 조정해주면, 앞서 말한 방법을 구현할 수 있습니다.

추가적으로 int 배열을 하나 더 선언하면 사이클을 찾았을 때 그 사이클에 포함된 정점의 개수가 몇개인지 dfs가 종료되었을 때 O(1)만에 알 수 있습니다.

정말 친절하게 설명해주셔서 감사합니다. 한번 해보겠습니다ㅠㅠ 정말 감사합니다.

댓글을 작성하려면 로그인해야 합니다.