[백트래킹 / Kotlin] BOJ 2580 - 스도쿠

문제

풀이 언어

Kotlin

코드

import java.util.*
import kotlin.system.exitProcess

lateinit var board: Array<Array<Int>>

fun main() = with(Scanner(System.`in`)) {
    board = Array(9) { Array(9) { 0 } }

    // 주어진 배열을 입력받음
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            board[i][j] = nextInt()
        }
    }

    // (0, 0) 부터 시작
    sudoku(0, 0)
}


fun check(row: Int, col: Int, value: Int): Boolean {
    // 1. 같은 행, 다른 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[row][i] == value) return false
    }

    // 2. 다른 행, 같은 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[i][col] == value) return false
    }

    // 3. (3x3) 블럭 내부에 같은 값이 존재하는지 확인
    // 현재 위치가 어느 위치의 (3x3) 블럭에 있는지를 우선 확인
    val r_index  = row / 3 * 3
    val c_index = col / 3 * 3

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (board[r_index + i][c_index + j] == value) return false
        }
    }

    return true
}

fun sudoku(row: Int, col: Int) {
    if (col == 9) {
        sudoku(row + 1, 0)
        return
    }

    if (row == 9) {
        val stringBuilder = StringBuilder()

        board.map {
            it.iterator().forEach { e ->
                stringBuilder.append(e).append(' ')
            }
            stringBuilder.append('\n')
        }

        println(stringBuilder)
        // 시스템 종료
        exitProcess(0)
    }

    if (board[row][col] == 0) {
        for (i in 1..9) {
            if (check(row, col, i)) {
                board[row][col] = i
                sudoku(row, col + 1)
            }
        }
        board[row][col] = 0
        return;
    }

    sudoku(row, col + 1)
}

풀이 방법

스도쿠는 아래와 같은 규칙을 갖는다.

1. 같은 행에는 1 ~ 9 가 중복 없이 존재한다.
2. 같은 열에는 1 ~ 9 가 중복 없이 존재한다.
3. 같은 블럭 (3x3) 에는 1 ~ 9 가 중복 없이 존재한다.

위 규칙에 따라 백트래킹 으로 구현한다.

 

하지만 중요한 것 이 한 가지 있다. 현재 좌측 상단부터 값을 넣어주는데 해당 위치의 값이 0 인 경우에 중복 여부를 판별하고 값을 집어넣지만 진행 과정에서 이 값이 잘못된 값이 될 수 있다. 가령 7이 들어가야 하는 자리에 위 조건을 만족한 다른 숫자가 들어가게 되면 이후의 모든 DFS 는 잘못된 값이 채워지게 된다. 따라서 해당 지점을 1 ~ 9 로 바꿔주되 이를 다시 0 으로 변경하여 모든 경우에 대해 탐색할 수 있도록 만들어줘야 한다. (처음 문제 풀 때 이 부분을 놓쳐서 값이 이상하게 출력되었다.)

 

1. 주어진 입력 값을 배열에 저장한다.

fun main() = with(Scanner(System.`in`)) {
    board = Array(9) { Array(9) { 0 } }

    // 주어진 배열을 입력받음
    for (i in 0 until 9) {
        for (j in 0 until 9) {
            board[i][j] = nextInt()
        }
    }

    // (0, 0) 부터 시작
    sudoku(0, 0)
}

 

2. (0, 0) -> (0, 1) ... 순으로 채워나간다. 이 때 해당 위치의 값이 0인 경우 어떤 값을 채워줄 지에 대해 판별한다.

    if (board[row][col] == 0) {
        for (i in 1..9) {
            if (check(row, col, i)) {
                board[row][col] = i
                sudoku(row, col + 1)
            }
        }
        board[row][col] = 0
        return;
    }

 

3. 스도쿠 규칙에 맞게 중복 값 여부를 판별한다.

fun check(row: Int, col: Int, value: Int): Boolean {
    // 1. 같은 행, 다른 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[row][i] == value) return false
    }

    // 2. 다른 행, 같은 열에 같은 값이 존재하는지 확인
    for (i in 0 until 9) {
        if (board[i][col] == value) return false
    }

    // 3. (3x3) 블럭 내부에 같은 값이 존재하는지 확인
    // 현재 위치가 어느 위치의 (3x3) 블럭에 있는지를 우선 확인
    val r_index  = row / 3 * 3
    val c_index = col / 3 * 3

    for (i in 0 until 3) {
        for (j in 0 until 3) {
            if (board[r_index + i][c_index + j] == value) return false
        }
    }

    return true
}

결과

참고 블로그

2580번 : 스도쿠 - JAVA