[백트랙킹] 2580번 스도쿠

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분 + a

1. 문제 설명

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

2580번: 스도쿠

2. 접근 방식

- 출처: https://hongcoding.tistory.com/118 참고 

1) 스도쿠 판에서 '0'에 해당하는 위치를 담은 리스트를 만든다.

2) 0을 담은 리스트를 하나씩 확인하면서 해당 위치에 값을 1~9까지 넣어본다.

3) 값을 넣고서 '행', '열', '3x3 박스'에서 1~9자리의 숫자가 중복되지 않는지 확인한다.

4) 0을 담은 리스트를 끝까지 다 확인했다면, 리스트를 출력하고 코드를 종료시킨다. 

3. 코드

board = [list(map(int, input().split())) for _ in range(9)]
blank = []

for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            blank.append((i, j))
             
def check_row(x, i):
    for v in range(9):
        if board[x][v] == i:
            return False
    return True

def check_col(y, i):
    for v in range(9):
        if board[v][y] == i:
            return False
    return True

def check_square(x, y, i):
    dx = x // 3 * 3
    dy = y // 3 * 3
    for a in range(3):
        for b in range(3):
            if i == board[dx+a][dy+b]:
                return False
    return True

def sdoku(idx):
    if idx == len(blank):
        for i in range(9):
            print(*board[i])
        exit(0)
    
    for i in range(1, 10): # 1~10인 이유는 스도쿠에는 1~9까지 입력이 가능하기 때문
        x = blank[idx][0]
        y = blank[idx][1]
        
        if check_row(x, i) and check_col(y, i) and check_square(x, y, i):
            board[x][y] = i # i값을 넣어본다.
            sdoku(idx+1)
            board[x][y] = 0 # 어디서든 False가 나오면 넣어뒀던 i 값을 뺀다.
sdoku(0)
# 출처: https://hongcoding.tistory.com/118

4. 코멘트

- 해당 문제는 도저히 감을 잡을 수 없다고 생각해서 다른 분들의 코드를 참고하게 됐다. 하지만, 코드르 살펴보면서 의외로 간단하다는 생각을 했던 것 같다. 결국 재귀적으로 문제를 푸는 것에 대한 두려움이 있었기 때문에 지레 겁을 먹는 것 같기도 하다.

- 위의 코드는 참고했던 블로그 코드 중에서 가장 직관적으로 문제를 풀었던 코드라고 생각한다.  

- 해당 코드를 돌려보면서, exit(0) 부분 때문에 계속 커널이 꺼져서 어쩔 수 없이 매번 9줄의 입력을 해야했던 게 꽤나 고역이였다...