코드의 몇몇 부분에 대한 조언을 드리고 싶습니다.
1. 함수 안에서 int check[100000] 등으로 지역변수를 할당하는 것은 일부 환경에서는 불가능할 수 있습니다 (런타임 에러의 가능성이 있습니다). 전역 변수로 선언하시는 걸 권장합니다.
2. vector<int> a[N]은 int a[N]으로 바꾸어도 상관없습니다. (왜일까요?)
3. 시간 초과가 나는 이유는 33번째 줄에 있는 반복문 때문입니다. DFS가 최대 v번 호출될 수 있고 반복문도 복잡도가 O(v)이므로 시간 복잡도가 O(v^2)입니다.
4. state와 check의 역할이 겹칩니다. state에 '이 정점을 몇 번째로 방문했는지'를 넣고 DFS를 이용해보세요. check 없이 state만으로도 문제를 해결할 수 있습니다.
5. 이 코드는 '틀렸습니다'가 나오는 예시도 있습니다. 이는 밑의 코드로 첨부하겠습니다.
joseph415 5년 전
시간초과가 계속 떠서 질문검색해서 확인해보니 초기화를 계속해줄필요가 없다 하셔서 check라는 배열을 따로 만들어서
싸이클이 형성되었으면 체크를 해서 더이상 dfs를 실행하지 않게 만들었는데 시간초과가 계쏙 뜹니다 ㅠㅠ
어떻게 바꿔야 할까요 ,,,