kkw564   4년 전

사이클 탐색을 1번부터 하면서 1->2->3->4->5->4 처럼 도중에 사이클이 발견되면

사이클 크기 2짜리가 있음을 반환하면서 6부터 시작하는데

이렇게 짜도 시간초과인데 어디까지 줄여야하죠 ..ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ도와주세요!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

chogahui05   4년 전

알고리즘을 먼저 설명해 주세요.

보통 visit는 방문하지 않은 노드는 0, 방문한 노드는 1로 해서 거르는 게 일반적입니다.


그리고.. 굳이 vector에 push_back하고, size를 구하고.. clear를 할 필요가 있을까요??

배열로 스택 같은 걸 구현하시고, dfs를 새로 수행할 때마다

포인터를 0으로 돌려놓으면 clear 효과를 매우 쉽게 낼 수 있습니다.

kkw564   4년 전

visit또한 memset을 안하기위해 각 테스트케이스마다 ++를해주어서 visit를 구분해주고있습니다

그러면 vector부분을 제외하고는 알고리즘 자체는 맞는건가요?


알고리즘은 다음과 같습니다

----

유니온 파인드의 파인드식으로 생각해서 풀었습니다.

우선 사이클이 존재하는지 노드 하나를 잡아서 돌면서 벡터에 현재 노드를 계속 담아줍니다.

사이클 탐색을 1번부터 하면서 1->2->3->4->5->4 처럼 도중에 사이클이 발견되면

사이클 크기 2짜리가 있음을 반환하면서 6부터 시작하는 이러한 방식을 이용했습니다.

---

chogahui05   4년 전

알고리즘 자체는..

어느 노드에서부터 탐색했는가?

만약 부모가 같은 노드들을 만나면 사이클이 있다.

이 두 아이디어를 떠올리면 됩니다. 거의 다 오신 거 같습니다.


어떻게 보면 집합의 find(); 와도 비슷해 보입니다. 만..

다른 것은 dfs를 처음 호출할 때, 부모가 결정된다는 것 정도가 되겠지요?

그렇기 때문에 잘 짜신다면 부모를 찾는 것도 O(1)이 될 거고요.


다만, 이게 잡다한 optimize를 적용하고도 700ms가 넘어가는 걸 보면..

데이터가 빡센 게 들어오는 듯 싶네요. 그 경우에는

함수 몇 개만 잘못 써도.. 시간 초과가 나기 딱 좋겠지요..

약간의 optimize도 요구하는 문제 같습니다.

kkw564   4년 전

역시 최적화를 조금 더 해 봐야겠군요..  감사합니다 또 궁금한게 생긴다면 가희님 아이디에 바로 뜰 수 있게 댓글로 질문드릴게요!! ㅋㅋ


감사합니다 문제에대해 생각해주셔서 ㅎㅎ

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