내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
백준 온라인 저지 (BOJ)
»
N-Queen
ps:problems:boj:9663
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== N-Queen ====== * 전형적인 N-queen 문제 * 최대 입력 사이즈가 15인데, 기본적인 백트래킹 구현만으로는 Python3의 시간제한을 맞추기 어렵다. 대칭을 이용한 속도 향상 테크닉이 들어가야만 통과 가능 * 그렇지만, 그냥 15까지의 모든 입력에 대한 답을 미리 구해놓고 그것을 그냥 출력해주는 꼼수로 52ms에 통과하는 것도 가능하다. ===== 풀이 ===== * [[:ps:N-queens]] 참고 ===== 코드 ===== ==== 코드 1 - backtracking ==== * 29076KB / 27556ms <dkpr py> """Solution code for "BOJ 9663. N-Queen". - Problem link: https://www.acmicpc.net/problem/9663 - Solution link: http://www.teferi.net/ps/problems/boj/9663 """ def solve(N, first_col): is_occupied_col = [i == first_col for i in range(N)] is_occupied_up_diag = [i == first_col for i in range(N * 2 - 1)] is_occupied_down_diag = [i == -first_col + N - 1 for i in range(N * 2 - 1)] def solve_rec(row): if row == N: return 1 count = 0 for col in range(N): u_diag = row + col d_diag = row - col + N - 1 if (is_occupied_col[col] or is_occupied_up_diag[u_diag] or is_occupied_down_diag[d_diag]): continue is_occupied_col[col] = True is_occupied_up_diag[u_diag] = True is_occupied_down_diag[d_diag] = True count += solve_rec(row + 1) is_occupied_col[col] = False is_occupied_up_diag[u_diag] = False is_occupied_down_diag[d_diag] = False return count return solve_rec(1) def main(): N = int(input()) answer = 0 for i in range(N // 2): answer += solve(N, i) * 2 if N % 2: answer += solve(N, N // 2) print(answer) if __name__ == '__main__': main() </dkpr> ==== 코드 2 - backtracking on permutation ==== * 29076KB / 15468ms <dkpr py> """Solution code for "BOJ 9663. N-Queen". Backtracking on permutation. - Problem link: https://www.acmicpc.net/problem/9663 - Solution link: http://www.teferi.net/ps/problems/boj/9663 """ def solve(N, first_col): cols = list(range(N)) cols[0], cols[first_col] = cols[first_col], cols[0] is_occupied_up_diag = [i == first_col for i in range(N * 2 - 1)] is_occupied_down_diag = [i == -first_col + N - 1 for i in range(N * 2 - 1)] def solve_rec(row): if row == N: return 1 count = 0 for i in range(row, N): col = cols[i] u_diag = row + col d_diag = row - col + N - 1 if is_occupied_up_diag[u_diag] or is_occupied_down_diag[d_diag]: continue cols[row], cols[i] = cols[i], cols[row] is_occupied_up_diag[u_diag] = True is_occupied_down_diag[d_diag] = True count += solve_rec(row + 1) cols[row], cols[i] = cols[i], cols[row] is_occupied_up_diag[u_diag] = False is_occupied_down_diag[d_diag] = False return count return solve_rec(1) def main(): N = int(input()) answer = 0 for i in range(N // 2): answer += solve(N, i) * 2 if N % 2: answer += solve(N, N // 2) print(answer) if __name__ == '__main__': main() </dkpr>
ps/problems/boj/9663.txt
· 마지막으로 수정됨: 2020/12/09 04:52 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로