너무나 기쁘다!
요근래 백트래킹에 대해서 공부를 했는데 쉬운문제가 아니었다.
바로 재귀함수를 제대로 이해하는것인가가 관건이기 때문이었다.
공부할 때 바킹독님 유튜브를 보면서 이해를 한다고 했는데도 참 어려웠다.
오늘 눈에 들어온게 스도쿠 문제
원래 스도쿠를 한번씩 풀기도 했고 재미있어서 한번 도전을 해보았다.
실제 푸는 방법은 다양하게 있지만 이 문제가 백트래킹과 어울릴 것 같다고는 생각했다.
처음에는 2차원배열로 했는데 바로 시간초과...
역시 배열은 난이도가 어려울수록 2차원 배열을 쓰면 안되는 것 같다.
따라서 1차원으로 값을 받느라 수학과 씨름을 했다.
아무래도 1차원을 가지고 2차원을 계산하려니 머리가 멘붕이었고 곱셈 나눗셈하고 친해졌다.(지금 생각해보면 배열 크기가 정해져 있어서 2x2를 해도 크게 상관은 없었을뜻? 하다.)
스도쿠값 체크 함수
func checkSudoku(index: Int, val: Int) -> Bool {
//스도쿠 빈 곳은 3가지 경우를 만족해야함
//같은 행에 같은 값은 존재하면 안된다.(1~9)
//같은 열에 같은 값 존재 안된다.(1~9)
//같은 3x3안에 같은 값 존재 안된다(1~9)
let row = (index/9)*9
let col = index%9
let posRow = row/27*27
let posCol = col/3*3
//같은 행 체크
for i in row ..< row+9 {
if index == i {
continue
}
if val == arr[i] {
return false
}
}
//같은 열 체크
for i in 0..<9 {
if index == col + (i*9) {
continue
}
if arr[col + (i*9)] == val {
return false
}
}
//같은 3x3 매트릭스 체크
for i in 0..<3 {
let startRow = (posRow)+(i*9)
for j in 0..<3 {
if index == startRow+(posCol+j) {
continue
}
if arr[startRow+(posCol+j)] == val {
return false
}
}
}
return true
}이제 이 함수를 가지고 재귀를 생각했는데 재귀함수는 은근히 쉬운줄 알았는데 이 때 삽질의 연속이었다.
백트래킹
func backTracking(index: Int) {
if isAllTrue() {
return
}
for i in index..<solveArr.count {
if isUsed[i] == false {
for val in 1...9 {
if checkSudoku(index: solveArr[i], val: val) {
isUsed[i] = true
arr[solveArr[i]] = val
backTracking(index: index+1)
/*삽질한 부분1*/
if isAllTrue() {
return
}
}
}
/*삽질한 부분2*/
isUsed[i] = false
arr[solveArr[i]] = 0
return
}
}
}재귀를 돌면서 값을 넣어야 하는 모든 곳에 값이 채워지지 않았고 몇 군데가 0으로 남기어져 있었다.
그래서 디버깅을 계속 해보면서(오늘 디버깅과 많이 친해졌다.) 문제를 파악했다.
빈 칸에 1부터 넣다보니 예를들어 7, 5 이런 식으로 넣었던 것이 틀렸으면 재귀를 돌아와서 7에 해당하는 값을 다시 1부터 넣어야 했는데 val이 6부터 시작되었다. 따라서 arr[solveArr[i]] = 0 를 꼭 해주어야 했다.
그리고 return으로 돌아왔을 때 모든 값이 채워져있다면 이 때부터는 계속 return을 시켜야하기 때문에 backTrackin(index: index+1) 아래에서 return을 할 것인지 혹은 isUsed와 arr[solved[i]] 값을 초기화 시킬 것인지 결정해 주었다.
6시간만의 정답!
지금까지 골드문제를 풀 때 항상 내가 푼적은 없고 결국 포기하고 남의 답안을 보면서 이해했는데 이번에는 내가 풀면서 어디가 잘 못 되었는지 디버그를 노가다하면서 어디가 문제였는지 스스로 이해하면서 혼자 풀어서 기분이 너무 좋았다. 제출하고 퍼센트가 올라갈 때마다 그 희열감은 너무 좋았고 "맞았습니다"가 나왔을 때는 소름이 돋았다. 그래서 이렇게 TIL을 남기게 되었다. 가성비가 좋은지는 모르겠지만 내 스스로 너무 만족하는 하루였다
