이 문제 해법을 고민한 끝에 오일러 회로를 구해야 한다는 결론에 이르렀습니다.

그래서 DFS를 이용해 오일러 회로를 구하는 코드를 작성했는데, 20%정도에서 시간초과가 발생합니다.

제가 예상하는 원인은 두가지로, 재귀호출 과정에서 stack overflow와 map의 성능 문제입니다.

(map은 이미 방문한 두 간선을 저장하는 과정에서 이용했습니다 - map을 이용하지 않고 짤 수 있는 기법이 있다면 알려주시면 감사하겠습니다!)

그런데 V와 E 모두 10만 이하라.. 깊이가 많아야 10만번 호출인데 stack overflow가 걸릴 수 있나요?

map이 아무리 느린 O(lgN) 이라지만 역시 제한이 10만인데 ㅠㅠ

뭐가 문제일까요! 알고리즘상의 문제일까요??

yukariko   4년 전

제 생각에 코드의 시간복잡도가 문제가 아니라면

map이 문제일 것 같습니다.

코드를 자세하게 보진않앗지만 

a->b로 가는 간선마다 index를 붙여서 관리하면

map이아닌 bool형 배열로 체크가 가능하지 않을 까 생각됩니다.

@yukariko

ㅠㅠ 하지만 맵을 쓰지 않아도 TLE는 개선되는 것 같지 않습니다.. ㅠㅠ

혹시 코드 한번만 더 봐주실 수 있나요? 아무리 생각해도 stack overflow는 문제가 아닐 것 같아서요 ㅠ

yukariko   4년 전

코드의 시간복잡도가 O(VE)가 아닌가요?

check 배열을 매번 초기화하고 탐색을 하다보니 시간초과가 날것같습니다.

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