BAEKJOON-2580 : 스도쿠

BEAKJOON-2580 : 스도쿠

아직 백트랙킹의 개념이 박히지 않았던 것 같다.

문제를 푸는데 상당히 많은 시간을 투자한 문제였다.

같은 문제를 몇 번이고 다시 풀어보니까 시도가 많아질 수록 문제 풀이에 가까워졌던 거 같다.

처음에는 문제 접근 방식이 아예 달랐고, 그 다음엔 유망한 후보를 거르게 되었고, 그 다음엔 dfs로 접근할 수 있게 되었다.

백트랙킹은 완전 탐색 방법에서 유망한 후보만 검사하는 방법인 것 같다.

코드

puzzle = [list(map(int, input().split())) for _ in range(9)]
point = [(i, j) for i in range(9) for j in range(9) if puzzle[i][j] == 0]

def is_promising(i, j):
    promising = [1,2,3,4,5,6,7,8,9]  
    
    for k in range(9):
        if puzzle[i][k] in promising:
            promising.remove(puzzle[i][k])
        if puzzle[k][j] in promising:
            promising.remove(puzzle[k][j])
            
    for p in range(i//3*3, (i//3+1)*3):
        for q in range(j//3*3, (j//3+1)*3):
            if puzzle[p][q] in promising:
                promising.remove(puzzle[p][q])
    
    return promising

flag = False
def dfs(n):
    global flag
    
    if flag:
        return
        
    if n == len(point):
        for row in puzzle:
            print(*row)
        flag = True
        return
        
    else:    
        i, j = point[n]
        promising = is_promising(i, j)
        
        for num in promising:
            puzzle[i][j] = num
            dfs(n + 1)
            puzzle[i][j] = 0 
dfs(0)

우선 스도쿠 퍼즐puzzle을 모두 입력받고, 빈 칸의 좌표를 배열point에 저장한다.

첫 번째 빈 칸의 좌표부터 탐색을 시작한다.

빈 칸에 숫자를 넣기 전에 답일 가능성이 있는 후보를 거른다.

행, 열, 9칸 안에 없는 숫자들을 걸러, 걸러진 수들을 후보로 한다.

그 후 후보들을 넣어가면서 그 다음 좌표를 탐색한다.