250x250
Notice
Recent Posts
Recent Comments
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 2022년 6월 일상
- 안드로이드 sunflower
- Fragment
- 막무가내
- 주엽역 생활맥주
- 막내의막무가내 프로그래밍
- 막내의막무가내 SQL
- flutter network call
- 막내의막무가내 rxjava
- 막내의막무가내 일상
- 막내의막무가내 코틀린 안드로이드
- 부스트코스
- 막내의막무가내 목표 및 회고
- 막내의막무가내 플러터 flutter
- 프로그래머스 알고리즘
- 안드로이드 Sunflower 스터디
- 막내의막무가내 코볼 COBOL
- 막내의막무가내 안드로이드
- 막내의막무가내 코틀린
- 막내의막무가내 안드로이드 코틀린
- 막내의막무가내 알고리즘
- 안드로이드
- 막내의 막무가내
- 프래그먼트
- 막내의막무가내 플러터
- 막내의막무가내 안드로이드 에러 해결
- 부스트코스에이스
- 막내의 막무가내 알고리즘
- 막내의막무가내
- 주택가 잠실새내
Archives
- Today
- Total
막내의 막무가내 프로그래밍 & 일상
[알고리즘] 프로그래머스 N-Queen -연습문제- -백트랙킹- 본문
728x90
https://programmers.co.kr/learn/courses/30/lessons/12952?language=kotlin
프로그래멋 LEVEL3 의 백트래킹 유형의 N-Queen 문제를 풀어봤습니다.
예전에 백준에서도 풀었었는데 아마 백트랙킹의 대표적인 문제라 프로그래머스에도 있는 것 같습니다.
복습할겸 다시한번 풀어봤습니다 ㅎㅎ
풀이는 다음과 같습니다.
[Java]
class Solution {
public static int N;
public static int answer = 0;
public static void main(String[] args) {
Solution solution = new Solution();
solution.solution(8);
}
public static void dfs(int[] map, int row) {
if (row == N) { //마지막행까지 다 놓은 경우
answer++;
} else {
for (int col = 1; col <= N; col++) {
map[row + 1] = col;
if (check(map, row + 1)) {
// 놓을 수 있는 자리인 경우 다음행으로 재귀
dfs(map, row+1);
}
}
}
}
public static boolean check(int[] map, int row) {
for (int i = 1; i < row; i++) { // 이전 행들 반복문
// 이전행의 같은 열에 체스가 있었는지
if (map[i] == map[row]) {
return false;
}
//대각선 공격 가능한지
if (Math.abs(i - row) == Math.abs(map[i] - map[row])) {
return false;
}
}
return true;
}
public int solution(int n) {
N = n;
for (int i = 1; i <= n; i++) {
int[] map = new int[n + 1];
map[1] = i;
dfs(map, 1);
}
return answer;
}
}
[Kotlin]
internal class Solution {
fun solution(n: Int): Int {
N = n
for (i in 1..n) {
val map = IntArray(n + 1)
map[1] = i
dfs(map, 1)
}
return answer
}
companion object {
var N: Int = 0
var answer = 0
@JvmStatic
fun main(args: Array<String>) {
val solution = Solution()
solution.solution(8)
}
fun dfs(map: IntArray, row: Int) {
if (row == N) { //마지막행까지 다 놓은 경우
answer++
} else {
for (col in 1..N) {
map[row + 1] = col
if (check(map, row + 1)) {
// 놓을 수 있는 자리인 경우 다음행으로 재귀
dfs(map, row + 1)
}
}
}
}
fun check(map: IntArray, row: Int): Boolean {
for (i in 1 until row) { // 이전 행들 반복문
// 이전행의 같은 열에 체스가 있었는지
if (map[i] == map[row]) {
return false
}
//대각선 공격 가능한지
if (Math.abs(i - row) == Math.abs(map[i] - map[row])) {
return false
}
}
return true
}
}
}
댓글과 공감은 큰 힘이 됩니다. 감사합니다~!
728x90
'알고리즘 > DFS, BFS, 시뮬, 백트래킹' 카테고리의 다른 글
[알고리즘] 프로그래머스 방문 길이 -Summer/Winter Coding(~2018)- (선을 방문하는 문제) (0) | 2020.05.18 |
---|---|
[알고리즘] 프로그래머스 타겟 넘버 -깊이/너비 우선 탐색(DFS/BFS)- (0) | 2020.05.16 |
[알고리즘] 프로그래머스 [1차] 프렌즈4 블록 -2018 KAKAO BLIND RECRUITMENT- (0) | 2020.05.11 |
[알고리즘] 프로그래머스 카카오프렌즈 컬러링북 -2017 카카오코드 예선, bfs, dfs- (0) | 2020.04.17 |
[알고리즘] 프로그래머스 카펫 -완전탐색- (0) | 2020.04.05 |
Comments