2022.06.22 「Lv.2 N-Queen」

이번 주는 코딩 테스트 연습에 더 박차를 가해볼 계획을 짰다. 다음 주에 모의 테스트를 볼 계획이므로 비중을 좀 더 둬봐야겠다. 이번 기회에 자료구조 한번 더 정리해볼 계획도 구상했다.

https://programmers.co.kr/learn/courses/30/lessons/12952

코딩테스트 연습 - N-Queen

 

문제 설명

가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.

예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한 번에 공격할 수 없습니다.

 

체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return 하는 solution함수를 완성해주세요.

 

제한사항

• 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
• n은 12이하의 자연수 입니다.

문제 풀이 과정

체스에서 퀸은 가로 세로 대각선으로 이동 가능하므로,  이미 배치 되어 있는 퀸과 만나는 세 가지 경우를 확인하며 진행하면 될 것 같다. 

가로줄을 기준으로 퀸을 추가하고, 세로와 대각선을 비교하면 좋을 것 같다. 

 

세로로 만날 경우

체스판은 하나의 좌표 평면과 같으므로 x, y 좌표계를 이용해 y 좌표의 값이 같은 값을 찾고 이 경우 탐색을 더 이상 진행하지 않는다. 

대각선으로 만날 경우

대각선은 기울기가 1, -1일 경우를 생각하면 된다. 이 때 서로의 퀸은 만나게 된다. 기울기 구하는 기본적인 수학 공식을 통해 진행하면 될 것이다.