문제
풀이 언어
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 ~ 9 가 중복 없이 존재한다.
- 같은 열에는 1 ~ 9 가 중복 없이 존재한다.
- 같은 블럭 (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
}
결과
참고 블로그
'✍️ 코테 준비 > Back Tracking' 카테고리의 다른 글
[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기 (0) | 2022.04.10 |
---|---|
[백트래킹 / Kotlin] BOJ 1987 - 알파벳 (0) | 2022.04.10 |
[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기 (0) | 2022.03.31 |
[백트래킹 / Kotlin] BOJ 9663 - N Queen (0) | 2022.03.29 |
[백트래킹 / Kotlin] BOJ 15649 ~ 15652 - N과 M (1 ~ 4) (0) | 2022.03.28 |