tlfla01   4년 전

그래프를 막 공부하고 있는 초보자입니다. 제가 작성한 소스에서 어디서 시간초과가 나는지 잘 이해가 되지 않아서 고수분들께 도움을 요청합니다. 제발 도와주세요 ㅜㅜ

kdk8361   4년 전

1

100000

2 3 4 5 6 ....... 99998 99999 100000 100000

이 케이스의 경우 i가 1부터 n까지 돌아갈 때 n, n-1, n-2, n-3,,,, 1

O(n^2)번 돌아갑니다.

bfs나 dfs를 돌린 후 그걸 초기화 하지 않고 그대로 써먹을 수 있습니다. 곰곰이 생각해 보세요

tlfla01   4년 전

아직 초기화를 한다는 생각을 버리지를 못해서요 ㅜㅜ

각 노드는 한개의 노드만 가리킨다는 생각을 기반으로 사이클이 아닌 경우 vector에 들어있는 노드들 중 마지막 노드만 해당 check를 초기화 시켜주어서 O(n^2) 으로 의심가는 초기화 반복문을 줄여봤는데 그래도 시간 초과가 뜨네요.. 혹시 조그마한 힌트 하나만 더 주실 수 있으신가요??

chogahui05   4년 전

한 사람이 2 사람 이상을 선택할 수 있을까요?

이 질문에 대한 답을 먼저 해 보시면 어떻게 푸셔야 할 지 아실 수 있을 듯 싶네요.


잘 안 되시는 경우에는 위상 정렬도 고려해 보세요.

특수한 케이스의 그래프에서는 사이클을 탐지하는 데 위상정렬을 써도 나쁘지 않습니다.

이 문제에 나오는 그래프 구조가 위상 정렬을 써도 되는 구조인지는 알려드리지 않겠습니다.

kdk8361   4년 전

정점에서 나가는(방향있는) 간선이 단 하나인 그래프일 경우 탐색을 하던 도중 이미 체크를 한 부분을 만났을 때

그 체크 했다는 사실이 어떤 의미를 가지는지, 의미가 있는지 없는지 한번 생각해 보시는게 좋을 것 같습니다.

이미 문제에 첨부되어 있는 예제가 아주 좋은 예제라고 생각해요.

tlfla01   4년 전

해당 소스에서 bfs로 풀던걸 dfs로 바꿔서 풀어봤습니다.

각 노드별로 돌다가 해당 경로가 사이클일때만 사이클임을 표기하는 새로운 함수를 돌리는 방법으로 구상해봤는데 다행히 돌아가더군요!!

답변주신분들 정말 감사드립니다!!

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