반응형
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/12952
코딩테스트 연습 - N-Queen
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은
programmers.co.kr
문제 설명
가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다.
예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 서로를 한번에 공격 할 수 없습니다.


체스판의 가로 세로의 세로의 길이 n이 매개변수로 주어질 때, n개의 퀸이 조건에 만족 하도록 배치할 수 있는 방법의 수를 return하는 solution함수를 완성해주세요.
제한사항- 퀸(Queen)은 가로, 세로, 대각선으로 이동할 수 있습니다.
- n은 12이하의 자연수 입니다.
풀이
2021.09.02 - [알고리즘 문제 풀이/백준] - 백준 9663 N-Queen Kotlin,c (백트래킹)
2021.09.21 - [알고리즘 문제 풀이/코뮤니티 추석맞이 코딩 챌린지] - [추석맞이 코딩챌린지 Bonus] 공격할 수 없는 Queen c
2021.12.02 - [알고리즘 문제 풀이/백준] - 백준 1799 비숍 Kotlin (백트래킹)
N-Queen 문제는 하도 많이 풀어서 이제 외울 지경이다.
위의 9663번 문제와 동일한 문제이니 자세한 풀이는 위의 글에서 확인!!
코드
class Solution {
var answer = 0
lateinit var colArr: IntArray
fun check(row: Int, col: Int, n: Int) : Boolean {
for(r in 0 until row){
//세로, 대각 있는지 체크
if(colArr[r] ==col || Math.abs(colArr[r] - col) == Math.abs(r-row) ) {
return false
}
}
return true
}
//백트래킹 함수 뎁스 한 번에 한 행만 탐색 -> 가로는 체크할 필요 없음
fun backTracking(row: Int, n: Int){
if(row==n){
answer++
return
}
for(i in 0 until n){
if(check(row,i,n)){
colArr[row] = i
backTracking(row+1,n)
colArr[row] = -1
}
}
}
fun solution(n: Int): Int {
colArr = IntArray(n){-1}
backTracking(0, n)
return answer
}
}
반응형
'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글
프로그래머스 파괴되지 않은 건물 Kotlin (누적 합) (0) | 2022.05.27 |
---|---|
프로그래머스 징검다리 Kotlin (이분탐색) (0) | 2022.05.25 |
프로그래머스 신고 결과 받기 Kotlin (문자열) (0) | 2022.05.06 |
프로그래머스 불량 사용자 Kotlin (순열, 비트마스킹) (0) | 2022.05.05 |
프로그래머스 징검다리 건너기 Kotlin (이분탐색) (0) | 2022.05.04 |
댓글