<백준> N-Queen(Gold 4)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/N-Queen

[백준]

https://www.acmicpc.net/problem/9663

아슬아슬했던 제출 결과

 

어떻게 하다보니 어제 풀었던 문제랑 동일한 문제를 풀게 되었다.

그런데 왜 이렇게 시간차이가 많이 나는지...? 이상했지만 보니까 백준은 14까지, 프로그래머스는 12까지였다.

거기에서 온 차이가 아닐까 싶다.

 

그래도 여기서 시간을 더 줄이기위해 노력한 부분은 분명히 있었다.

전에는 위쪽 대각선도 생각하고 처리를 했었는데 생각해보면 위에서부터 차례대로 내려오기 때문에 처리할 필요가 없었다.

이 부분 제거했고 첫번째 줄에 대한 처리도 재귀함수에 넣는 방식을 채택했다.

이렇게 푸니까 약간 복습하는 것 같아서 좋았지만 다른 사람들이 많이 푸는 방식은 아직 이해가 잘 안되더라

1차원 배열로 푸는 방식인데 인덱스가 행, 값이 열이 되고 지금 놓은 자리가 놔도 괜찮은 자리인지 체크하는 알고리즘이었다.

앞의 배열에 값을 지정하는 건 이해가 잘 됐는데 지금 놓은 자리가 놔도 괜찮은 자리인지 체크하는 방식은 아직 잘 이해가 되지 않는다.

행을 돌면서 열의 값이 같거나 행끼리의 차이의 절댓값과 열끼리의 차이의 절대값이 같다면 false를 리턴하고 아니면 true를 리턴한다.

가로체크는 당연히 그 전까지의 행만 순회하면되니까 오케이

세로체크는 열의 값 체크로 오케이

대각선체크가 조금... 잘 이해가 안 되네

그래도 어느정도 느낌이 이제 오는건 대각선이라는거는, 특히 지금 문제에서 원하는 대각선이라는 거는 가로세로 길이의 비율이 1대1인 두변을 가지는 대각선이기 대문에 차이의 절대값을 비교하는 것 같다.

이렇게 푸는 거 또 나중에 기회가 있겠지...

잘 기억하고 있어야겠다.

2차원 배열을 만드는 것이 아니라 1차원 배열에 행과 열의 정보를 넣는 방식..!!

 

배열의 값을 바꿀 때 약간 이슈가 있었는데 forEach로 배열을 순회하면서 조건에 맞을 때 해당 위치의 값을 바꾸려고 하니까 Val cannot be reassigned 에러가 뜨더라

그 이유는 실제 데이터가 아닌 참조만 할 수 있는 형태로 it을 사용하기 때문인 거 같다.

이걸 해결하기 위해서는 인덱스를 도는 형태인 for문을 사용하면 됐다.

 

해당 방법으로 작성한 코드는 다음과 같다.

private lateinit var chessBoard: Array<Array<Int>>
private var n = 0
private var answer = 0
fun main() = with(System.`in`.bufferedReader()) {
    n = readln().toInt()
    chessBoard = Array(n) { Array(n) { 0 } }

    deployQueen(0)
    println(answer)
}

fun deployQueen(row: Int) {
    if (row == n) {
        answer++
        return
    }

    for (i in 0 until n) {
        if (chessBoard[row][i] == 0) {
            setAttachRange(row, i)
            deployQueen(row + 1)
            deleteAttackRange(row)
        }
    }
}

fun setAttachRange(row: Int, col: Int) {
    for (i in chessBoard.indices) {
        if (chessBoard[row][i] == 0) chessBoard[row][i] = -(row + 1)
        if (chessBoard[i][col] == 0) chessBoard[i][col] = -(row + 1)
    }

    var r = 1
    var c = 1
    while (row + r < n && col + c < n) {
        if (chessBoard[row + r][col + c] == 0) chessBoard[row + r][col + c] = -(row + 1)
        r++; c++
    }

    r = 1
    c = 1
    while (row + r < n && col - c >= 0) {
        if (chessBoard[row + r][col - c] == 0) chessBoard[row + r][col - c] = -(row + 1)
        r++; c++
    }
}

fun deleteAttackRange(row: Int) {
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (chessBoard[i][j] == -(row + 1)) chessBoard[i][j] = 0
        }
    }
}