temp   8년 전

저번에 탐색하지 못한 부분에 대하여 다찾게는 해놨는데..

dfs탐색이 상당히 비효율적이네요. 알고는 있으나 수정하기가 정말 애매하네요.

check함수를 호출하지않으면 완전히 탐색이 되긴하는데 check를 하는순간 타임이 오버납니다. 

어떻게 수정사항이 없을까요? 그냥 포기하고 25개중 7개를 뽑는 경우를 만드는게 빠를까요?

yukariko   8년 전

최적화를 위한 첫 번째 생각은

check에 사용되는 POS의 7칸 짜리 배열을 비트마스크를 통해 int형 하나로 바꾸는 것입니다.

5*5 격자이니 총 25개의 비트가 존재하게 되고, 각 위치에 1을 마킹해주면 7 * 7 의 반복문이 if문 비교 하나로 바뀌게 됩니다.


두 번째 생각은 위 int로 바뀐 check변수를 set이나 map으로 저장하는 것입니다. 

이렇게 되면 지금의 선형비교가 로그비교로 바뀌게 됩니다.

한가지 다른 생각은 2^25 크기의 배열을 선언해 check를 바로 수행하는것입니다.

이 경우는 상수비교지만, 배열의 크기가 커서 bool형 기준 34MB 가 나오네요. (bitset을 이용하면 메모리를 8배 줄일 수 있습니다.)



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