9663

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 대표적인 백트래킹 문제다. 퀸을 2차원 리스트 체스판에 놓을 수 있는 경우는 다음과 같다. 1. 이전까지 놓은 퀸들이 같은 행에 없는 경우 2. 현재 놓으려는 퀸의 이전 대각선에 퀸이 위치하지 않는 경우 그래서 1번, 2번 조건을 각각 만들어줬다. # 9663번: N-Queen n = int(input()) visited = [[False] * (n+2) for _ in range(n+2)] visited_row = [False] * (n+2) # 1~n번 행에 퀸이 놓였는지 ..

9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 심화문제다. 2차원 배열이 나오는 문제라 2차원 배열을 백트래킹해야 한다고 생각할 수도 있는데 아니다. 일단 처음 풀이 방법을 생각해봤을 때도 굳이 2차원 배열을 백트래킹하지 않아도 될 것 같다는 생각이 들었다. 그래서 첫 풀이 코드가 나왔다. (틀린 풀이) # 9663번: N-Queen n = int(input()) visited = [False] * (n+1) count = 0 def backTracking(depth, prev_num): if depth == n:..