qkrtjdrb9573   3년 전

문제에서 주어진 케이스에 대해 13,14가 너무 늦습니다

시간을 획기적으로 줄일 수 있는 방법은 어떤 게 있고 적용하려면 제 코드에서 어떤 부분을 수정해야 할까요

코딩 잘하시는 분들, 이 불쌍한 영혼을 도와주세요!!

zlzmsrhak   3년 전

여러가지 컷팅 알고리즘이 있습니다.

1. 퀸을 N개 놔야 한다는 조건 때문에, 모든 행과 모든 열에는 퀸이 하나씩 있어야 합니다.

이 때문에, 행을 기준으로 한 DFS도 성립합니다. 

첫 번째 행에 하나를 놓아보고, 두 번재 행에 하나를 놓아보고, ... 하는 식으루요.

2. 퀸을 놓을 수 있는지 없는지를 확인할 때는, 각 행, 열 대각선에 퀸이 있는지를 체크하는 식으로 확인 가능합니다.

예를 들어, 세 번째 대각선에 퀸을 놓았다면, 세 번째 대각선에 퀸이 있다고 체크하는 식입니다.

이러면 다음에 퀸을 놓을 때 배열을 확인해서, 세 번째 대각선에 퀸이 없다는 것을 알 수 있겠죠. 

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