9663번 - N-Queen
파이썬으로 동일하게 코드를 짰다가 시간초과로 C++로 작성해보았습니다. 에디터 상에서 답은 확실히 C++코드가 빨리 나오긴 하는데 채점해보니 둘다 시간초과 뜨는 것은 마찬가지네요... 어느 부분에서 개선하면 좋을지 리뷰 부탁드립니다!
놓을 수 있는 자리인지 판단하는 함수인 Promising이 너무 오래걸리는 것 같습니다.
굳이 모든 판을 훑지 않아도 빠르게 판별할 수 있는 방법이 있습니다.
예를들어 특정 세로줄에 퀸이 존재하는지 기록하는 배열을 만들어서 해당 줄을 보면 바로 알 수 있겠지요.
대각선도 마찬가지 방법으로 해결 하실 수 있을겁니다.
답글 감사합니다.
하나만 더 여쭤봐도 될까요?
nqueen 문제는 보통 일차원 배열로 각 행에 있는 퀸의 열만 저장해서 판별을 하는 방법이 정석이던데
말씀해주신 방법대로 promising을 개선하면 2차원 배열 선언으로도 해결이 가능할지 궁금합니다.
제가 말한 방식은 2차원 배열이 필요 없는 방식입니다.
특정 가로줄, 세로줄, 대각선줄마다 퀸이 최대 1개 존재하므로 2차원 배열을 1차원으로 압축시켜 빠르게 확인 할 수 있게 하는 것이죠.
2차원 배열을 그대로 사용하고 싶으시다면 대각선을 확인하는 과정에서 모든 판을 훑는게 아니라, 양 대각선 쪽만 탐색하는 식으로 좀더 최적화가 가능하긴 합니다.
제 코드가 0.9초 정도 걸려서 통과했었는데 그것보다 최대 16배정도 느리니까 통과하기 애매하지 않을까 생각이 듭니다.
참고해보겠습니다.
댓글을 작성하려면 로그인해야 합니다.
dusrlf13 3년 전
파이썬으로 동일하게 코드를 짰다가 시간초과로 C++로 작성해보았습니다. 에디터 상에서 답은 확실히 C++코드가 빨리 나오긴 하는데 채점해보니 둘다 시간초과 뜨는 것은 마찬가지네요... 어느 부분에서 개선하면 좋을지 리뷰 부탁드립니다!