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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

백트래킹 문제다.

 

풀이

실제로 스도쿠를 풀듯이 각 칸에 대한 숫자 대입 여부를 확인하면 된다. 그걸 어떻게 구현하느냐가 문제의 핵심. 결국 생각이 나지 않아 다른 분의 풀이에서 힌트를 얻고 문제를 풀었다.

스도쿠 판의 각 열, 행, 사각형에 1부터 9를 대입할 수 있는 2차원 배열을 생성한다. 입력받은 스도쿠 탐색 시 0을 마주하였을 경우 앞에서 생성한 3개의 배열에 대입하려는 숫자에 해당하는 인덱스가 모두 false인 경우, 숫자를 현재 좌표에 대입 후 재귀 호출, 해당 숫자가 답이 아닐 수 있으므로 0으로 복구시킨 후 다음 탐색을 수행한다.

마지막 좌표에 도달하면 스도쿠를 출력하면 된다.

정답 코드

import Foundation
var row = Array(repeating: Array(repeating: false, count: 10), count: 10)
var col = Array(repeating: Array(repeating: false, count: 10), count: 10)
var rect = Array(repeating: Array(repeating: false, count: 10), count: 10)
var map = Array(repeating: Array(repeating: 0, count: 9), count: 9)
var flag = false
for i in 0..<9{
let line = readLine()!.split(separator: " ").map{Int($0)!}
for k in 0..<9{
map[i][k] = line[k]
if map[i][k]>0{
let num = map[i][k]
row[i][num] = true
col[k][num] = true
rect[(i/3)*3+(k/3)][num] = true
}
}
}
func btk(cnt:Int){
if flag{ return }
let x = cnt/9
let y = cnt%9
if cnt == 81{
for numbers in map{
for number in numbers{
print(number, terminator: " ")
}
print()
}
flag = true
return
}
if map[x][y] > 0{
btk(cnt: cnt+1)
}else{
for num in 1..<10{
if !row[x][num] && !col[y][num] && !rect[(x/3)*3+(y/3)][num]{
row[x][num] = true
col[y][num] = true
rect[(x/3)*3+(y/3)][num] = true
map[x][y] = num
btk(cnt: cnt+1)
map[x][y] = 0
row[x][num] = false
col[y][num] = false
rect[(x/3)*3+(y/3)][num] = false
}
}
}
}
btk(cnt: 0)
view raw 2580.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[18116] 로봇 조립  (0) 2022.12.09
[3190] 뱀  (0) 2022.12.08
[11559] Puyo Puyo  (0) 2022.12.05
[17070] 파이프 옮기기 1  (8) 2022.12.01
[12851] 숨바꼭질 2  (0) 2022.11.30

+ Recent posts