coacervate   10달 전

최대한 시간을 줄여본다고 애썼는데, 11%에서 시간초과가 납니다.

구현 방식은

1. 처음에 행(row) 별로 빠져있는 숫자에 대해 candidate 를 만들고, 빠진 위치를 omit_coord에 열(column) 값만 저장했습니다.

2. 백트래킹 함수는 0행으로 시작해서, 매 행마다 위에서 만들어놓은 candidate를 next_permutation을 이용해 계속 위치를 수정하여 뿌립니다.

3. 2번에서 값을 뿌리면서 열, 그리고 블록의 값과 겹치는지 확인 후, 만약 겹친다면 다음 next_permutation으로 넘어가고, 겹치지 않는다면 해당 row를 선택하고 다음 row로 넘어갑니다. (재귀 호출)

4. 이렇게 계속 해서 0~8행을 다 보고 row 값이 9가 되면,    2, 3의 과정을 통해  매 행마다 유효성 검사를 하였으므로,  별다른 검사 없이 전체 table을 출력하고 프로그램을 종료합니다.

5. 만약 어떤 row에서 유효성 조건을 충족하지 못 해 더 이상 넘어 갈 수 없는 경우, 3번으로 다시 돌아가 다음 next_permutation으로 넘어갑니다 (백트래킹)

이렇게 생각을 해 보았는데요, 질문 게시판에 있는 TC를 여러 개 돌려본 결과 답이 다 나오는 것 같습니다. (0으로만 채워져 있는 것 포함)

시간 복잡도는 9! ^ 9!.....인것 같긴 한데 이렇게 푸는 게 아예 잘못된 걸까요 ㅠㅠ

제 코드에서 어느 부분이 시간을 많이 잡아먹는지 알고 싶습니다.

+ 시간초과 나는 TC를 알고 싶습니다...

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