jeongbeen   8달 전

1
3
2 3 2

1 -> 2 -> 3 -> 2
dfs(1)일 때 check[1], check[2], check[3]에 1을 넣어 방문표시를 하고,
큐에 1,2,3을 넣어주었습니다.
그 이후 다시 2를 만나면 이미 방문한 곳이므로 dfs를 멈추고,
큐에서 값을 하나씩 꺼내어 사이클을 만드는지 확인했습니다.

위와 같이 풀면
dfs에 O(n), dfs함수 안에서 큐가 빌 때까지 돌아가는 반복문 O(n)
따라서 O(n^2) 이라고 생각했습니다.

질문 게시판의 다른 글들을 보면 O(n^2)로는 통과를 못하는 것 같은데,
시간 복잡도를 잘못 구한걸까요? 왜 맞은건지 궁금합니다.

감사합니다.

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