jo2203   11달 전

12 약간 느리게 나오는데 13부터는 굉장히 느리게나오네요.....

코드를 간단히 설명해 드리면


N개의 퀸은 모두 모든 칸 , 모든 줄에 1개가 있어야 함으로

맨 아랫줄부터 놓을 수 있는곳을 판단하고 다음줄을 판단합니다.

만약 다음줄에서 놓을 수 있는 경우가 없다면 해가 없는경우라 판단하고 더이상 탐색하지 않습니다.

나름 탐색 범위를 많이 줄였다고 생각했는데 시간초과가 나와서 너무 슬프네요.

퀸을 놓고 퀸의 공격범위를 모두 1로 표시합니다.

(아래는 1로 표시 하지 않습니다. 맨아랫칸부터 한칸씩 올라가기 때문에 의미가 없으므로)


시간초과의 의미로는 각 케이스에서 vector를 인자로 받는데 이때 복사가 많으므로 느려지는것을 생각하고 있는데...

안된다고 생각된 범위를 다시 0으로 표현하는것보다 vector를 날리는게 더 시간이 짧게 걸리지 않을까요???


가독성도 별로 안좋은 코드지만 답변해주시면 감사하겠습니다 ㅠㅠ

show981111   11달 전

퀸을 하나 놓을때마다 가로,세로,대각선을 모두 돌며 1로 체크해주는 부분이 느린것 같습니다... 차라리 세운 퀸들의 위치를 저장한 뒤에, 새로운 위치와 기존의 퀸들의 위치를 비교하는게 더 빠를것같네요. 대각선의 경우 abs(dy) == abs(dx) 이러한 수식으로 빠르게 판단할 수 있습니다!..

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