9663:N-Queen [백준 문제풀이][Python][CLASS 4]
문제:https://www.acmicpc.net/problem/9663 n*n 격자판 위에 n개의 퀸을 배치할때, 퀸이 서로를 공격하지 못하게 배치하는 경우의 수를 구하시오.백트래킹을 이용하는 굉장히 유명한 문제이다.아이디어백트래킹을 이용해서 위쪽 줄부터 차례대로 재귀함수를 사용해 탐색하면서 내려가면 된다.이때 겹치는 세로줄,대각선을 체크하여 들어갈 수 있는지 확인하기 위한 리스트를 만든다. 우하향,우상향 대각선을 분리해서 생각해주었다. 퀸이 있는 자리에 배열 값을 바꿔주면서 내려와서 마지막줄에 도달하면, count +=1을 해주어 개수를 세었다.각 x,y에서 col1,diag1,diag2의 어떤 값이 올지 생각해주는게 관건이었던거 같다.정답 코드n=int(input())col1=[0]*n#세로diag1..
2024.07.05