[Swift] 백준_스도쿠(2580)

문제

 

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

2580번: 스도쿠

 

 

풀이

 

N-Queen에서의 접근방법을 떠올리며 풀었었다. 

0인 칸에 숫자가 채워지면 해당 칸을 포함하는 행과 열 그리고 해당 블럭(3x3)에서 그 숫자는 유일해야한다. 따라서 세 개의 변수를 선언하였다.

각 행과 열 그리고 블럭 안에는 1부터 9까지의 수가 한 번씩만 들어가야하므로 이차원배열을 이용했다. 예를 들어, 2번째 열에 3이라는 숫자가 들어간다면 row[1][3] = true가 되는 것이다.

block은 위에서부터 위에서부터 0,1,2 / 3,4,5 / 6,7,8 로 생각하였다.

 

우선, 입력으로 받은 보드를 확인하며 0이 아닌 칸에는 row, col, block변수에서 값을 true로 바꿔주었다. 각 칸이 어떤 블럭에 들어가는지는 ( i / 3) * 3 + j / 3으로 하면 알 수 있었다.

 

다음으로 보드를 돌면서 체크를 해야하는데, 여기서 막혔었다.

처음에는 0인 칸의 좌표를 이용하였다. zero라는 배열안에 0인 점들의 좌표를 넣어준 뒤, 반복문을 통해 각 칸에 숫자를 1부터 9까지 넣어가면서 dfs를 이용해 값을 구했다. 하지만 이렇게 하니 반복문의 중첩이 불가피하며 결국엔 시간초과가 나왔다.

 

그래서 다른 방법을 찾아보니 아예 모든 점을 확인해서 해결할 수 있었다. 0이 아니라면 그대로 count에 1만 더해준채로 이어가고, 0인 경우에는 조건을 만족한다면 이어서 진행하도록 하는 것이었따. 여기서 내가 생각하지 못했던 것은 count로 좌표를 구할 수 있다는 점이었다.

9로 나눈 몫이 i(x)의 좌표가 되고, 9로 나눈 나머지가 j(y)의 좌표가 된다.

 

이를 이용해 진행하다가 count가 81이 되면 완성되었다는 뜻이므로 print를 해준 뒤에 exit(0)을 통해 종료해주었다. 답이 여러 개일 수도 있기 때문에 exit으로 종료해야한다.

import Foundation

var board: [[Int]] = []
var row = Array(repeating: Array(repeating: false, count: 9), count: 9)
var col = Array(repeating: Array(repeating: false, count: 9), count: 9)
var block = Array(repeating: Array(repeating: false, count: 9), count: 9)
for _ in 0..<9 {
    board.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

for i in 0..<9 {
    for j in 0..<9 {
        if board[i][j] != 0 {
            row[i][board[i][j] - 1] = true
            col[j][board[i][j] - 1] = true
            block[(i / 3) * 3 + j / 3][board[i][j] - 1] = true
        }
    }
}
func dfs(_ count: Int) {
    let idxI = count / 9
    let idxJ = count % 9
    if count == 81 {
        board.forEach {
            print($0.map { String($0) }.joined(separator: " "))
        }
        exit(0)
    }
    if board[idxI][idxJ] != 0 {
        dfs(count + 1)
    } else {
        for i in 0..<9 {
            if !row[idxI][i] && !col[idxJ][i] && !block[(idxI / 3) * 3 + idxJ / 3][i] {
                row[idxI][i] = true
                col[idxJ][i] = true
                block[(idxI / 3) * 3 + idxJ / 3][i] = true
                board[idxI][idxJ] = i + 1
                dfs(count + 1)
                row[idxI][i] = false
                col[idxJ][i] = false
                block[(idxI / 3) * 3 + idxJ / 3][i] = false
                board[idxI][idxJ] = 0
            }
        }
    }
}
dfs(0)

 

 

_____________________________________________________________________________________________________

 

 

백트래킹 문제 어렵다. 많이풀어야함