beomyoung93   2년 전

단순히 답만 맞고 시간초과가 발생하는 부분을 못 짚겠습니다.

분명 불필요한 과정을 반복하는 부분이 있는거 같은데 그 부분을 못 찾겠습니다 ㅠㅠ


1) backtrack() 함수의 for()문

2) 서로 공격가능한 위치를 탐색하는 isPossible() 함수

이 두 부분에서 뭔가 잘못한거 같은데... 잘못된 부분을 캐치를 못 하겠습니다.

srand   2년 전

isPossible 함수에서 중복 검사를 조금 더 빠르게 바꾸시는건 어떨까요?

예를 들면 열 검사 의 for loop 대신, 

char check_column[ 가로크기 ] = { 0 , } 과 같은 변수를 둬서 

퀸을 둘 때 check_column[ 퀸 가로 위치 ] = 1 로 셋팅

검사는 check_column[ 가로 위치] == 1 ?

등등


가로, 세로, 우측 아래 대각선, 우측 위 대각선 검사를 빠르게 하면 

수행 속도가 빨라질 것으로 예상 됩니다.

112224   2년 전

isPossible 함수에서 위치검사할때 수행횟수가 너무 많아서 그러실 거에요.

기울기 양,음에 관계없이 대각선이 한번에 검사가 가능한데, 별거 아닌 차이지만

문제의 시간복잡도 자체가 워낙 크다보니(대략 O(n^n)정도) 그 부분 하나로 TLE 받으신 것 같습니다!

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