[Kotlin] BOJ9663 N-Queen

처음에는 따로 Point라고 Data class를 만들어서 

조건을 만족하는 자리를 만나면 해당 객체에 좌표를 보관하는 식으로 문제를 풀었엇는데

계속해서 메모리 초과가 나왔다. 

메모리를 어떻게하면 줄일 수 있을까 하고 계속해서 고민해보고 허탕치다가

데이터클래스를 안쓰고 colum값만 저장하는 방식으로 푸니까 풀렸다.

 

교훈 : DFS풀때 data class(객체) 사용하면 메모리를 생각보다 많이 잡아먹으니 감안하고 코드를 짜자!

(data class 뿐만아니라 Pair 사용해도 메모리를 많이 먹으니 메모리 커트라인이 넉넉하지 않다면

그냥 객체 사용을 지양하는게 좋을듯 하다.)

 

 

(링크 : https://www.acmicpc.net/problem/9663)

9663번: N-Queen

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
lateinit var stack :ArrayList<Int>

var N = 0
var count = 0
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    N = br.readLine().toInt() //1~14
    stack = ArrayList<Int>()

    for (i in 0 until N){
        dfs(0,i)
    }

    println(count)
}

private fun dfs(
    row :Int,
    col :Int
){
    //체크인
    stack.add(col)
    //목적지인가? -> row = N -1
    if (row == N-1) {
        count++
        stack.removeLast() //체크아웃
        return
    }
    //연결된 곳 순회
    for (i in 0 until N){
        //갈 수 있는가? -> 다른 퀸의 대각 ,좌우, 상하로 부터 안전한가
        if (checkQueen(row +1,i)){
            //간다.
            dfs(row +1,i)
        }
    }
    //체크아웃
    stack.removeLast()
}

private fun checkQueen(
    row :Int,
    col :Int
):Boolean{
    for ((index , queenCol) in stack.withIndex()) {
        //상하
        if (queenCol == col) return false
        //대각(기울기 1, -1)
        if(Math.abs(queenCol - col) == Math.abs(index - row)) return false
    }
    return true
}

 

메모리 초과나오던 코드

import java.io.BufferedReader
import java.io.FileInputStream
import java.io.InputStreamReader
lateinit var stack :ArrayList<Point>

var N = 0
var count = 0
fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    N = br.readLine().toInt() //1~14
    stack = ArrayList<Point>()

    for (i in 0 until N){
        dfs(0,i)
    }

    println(count)
}

private fun dfs(
    row :Int,
    col :Int
){
    //체크인
    stack.add(Point(row, col))

    //목적지인가? -> row = N -1
    if (row == N-1) {
        count++
        //체크아웃
        stack.removeLast()
        return
    }
    //연결된 곳 순회
    for (i in 0 until N){
        //갈 수 있는가? -> 다른 퀸의 대각 ,좌우, 상하로 부터 안전한가
        if (checkQueen( Point(row +1, i) )){
            //간다.
            dfs(row +1,i)
        }
    }
    //체크아웃
    stack.removeLast()
}

private fun checkQueen(
    point :Point
):Boolean{

    for (queen in stack) {
        //상하
        if (queen.col == point.col) return false
        //대각(기울기 1, -1)
        if(Math.abs(queen.col - point.col) == Math.abs(queen.row - point.row)) return false
    }
    return true
}

class Point(val row :Int, val col :Int)