[알고리즘] 스도쿠 2 - 스도쿠 풀이 (백트래킹, DFS)

leetcode.com/problems/sudoku-solver/

Sudoku Solver - LeetCode

 

백트래킹이란,

맞는 답을 먼저 찾는 대신

일단 후보를 입력하고 답인것 처럼 진행하다가 조건이 안맞는 경우가 생기면 다시 되돌아와서 다른 후보값을 입력하는 방식으로 답을 찾는 알고리즘이다.

가지치기 (pruning) 처럼 답이 아닌 것들을 후보에서 제거하여 경우의 수를 줄여나가 답을 찾는 접근

 

 

recursive 를 사용하는 것이 DFS 랑 비슷하다.

DFS 는 모든 그래프를 탐색하는 것이 목표이기 때문에 백트래킹과 완전 같다고는 할 수 없지만,

DFS와 백트래킹을 혼용하여 조건이 안맞는 부분은 탐색하지 않으므로써 런타임을 줄일 수 있다.

 

 

Approach

스도쿠 1 포스팅에서 썼던 것 처럼 valid 한지 아닌지는 검색에 O(1) 밖에 소요되지 않는 HashSet을 썼다.

스도쿠 문제 검증 포스팅 - developer-hongjoo.tistory.com/30

 

힌트를 HashSet 안에 다 넣은 다음,

Fill( ) 을 call 하여 백트래킹을 시작하였다.

 

Fill( )은 스도쿠 첫번째 칸 board[0][0] 부터 board[8][8] 까지 훑으면서

board의 value 가 '.' 이면 후보값을 체워 넣기 시작한다.

 

넣은 후보 값이 valid 하면 다음 칸 (= [x][y+1] 다음 인덱스로 자기 자신을 호출 ),

valid 하지않으면 다음 loop로 넘어가서 다음 숫자를 후보로써 체크하고

모든 숫자가 다 valid 하지않으면 (= loop가 끝나면 ) false 를 return 하여 현재 보고 있는 board[x][y] 의 이전 칸인 board[x][y-1]으로 돌아간다. (= recursive 이기 때문에 저절로 돌아가 자기자신을 호출한 다음 소스부터 다시 진행된다)

 

그렇기 때문에, false 가 리턴되면 그동안 추가되었던 HashSet과 board value를 리셋해줘야한다.

 

전체소스

 

 

 

비슷한 문제 : leetcode.com/problems/word-search/

Word Search - LeetCode