[백준] 2580번: 스도쿠

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

2580번: 스도쿠

 

처음에는 이렇게 풀었었는데, 문제에 제시된 테스트 케이스만 통과했어서, 

결국 풀이를 찾아봤다.

 

import sys
from collections import deque
input = sys.stdin.readline

def backtracking(y, x): # 좌표
    if matrix[y][x] != 0:
        return

    for i in range(1, 10):
        endflag = True

        # 가로줄, 세로줄 검사
        for j in range(9):
            if matrix[y][j] == 0:
                queue.append((y, j))
            if matrix[j][x] == 0:
                queue.append((j, x))

            if matrix[y][j] == i or matrix[j][x] == i:
                endflag = False
                break

        # 3x3 정사각형 검사
        for row in range((x // 3) * 3, (x // 3) * 3 + 3):
            for col in range((y // 3) * 3, (y // 3) * 3 + 3):
                if matrix[col][row] == 0:
                    queue.append((col, row))

                if matrix[col][row] == i:
                    endflag = False
                    break

        if endflag:
            matrix[y][x] = i
        else:
            continue

    if queue:
        ny, nx = queue.popleft()
        backtracking(ny, nx)
    else: # 더이상 빈칸이 없음
        return

queue = deque() # 빈 칸의 좌표를 저장할 queue
matrix = [list(map(int, input().split())) for _ in range(9)]

for i in range(9):
    for j in range(9):
        if matrix[i][j] == 0:
            backtracking(i, j)

# 답 출력
for i in range(9):
    for j in range(9):
        print(matrix[j][i], end=" ")
    print()

처음에는 deque 자료구조에 빈 칸을 모두 넣고 하나씩 pop해서 풀려고 했는데, 

그렇게 하면 해당 숫자가 그 자리에 올바르지 못한 숫자일 경우 다시 초기화하는 코드가 없어서 

제대로 답을 도출해 낼 수 없는 것이 아닐까?

 

backtracking함수를 재귀 호출 후 왜 스도쿠 판을 초기화시켜야 하는지 이해가 안갔었는데,

좀 더 생각해보니까 backtraking함수 호출 밑의 코드는 답을 찾지 못한 경우에만 실행이 되는 것이므로

다른 숫자를 넣어볼 수 있게 0으로의 초기화가 필요한 것 같다.

 

답을 찾았을 경우 return 문이 아닌 exit()문을 써야 하는 이유도 궁금했는데,

직접 return문으로 바꿔보니까 return문으로 빠져나가면 backtraking 함수를 호출하고 나서의 코드가 실행되어 무한루프에 빠질 수 있기 때문이었다.

이걸 직접 해봐서 깨닫다니 솔직히 좀 바보같았던거같다ㅋㅋㅋ😂

 

 

참고
2580번 풀이: https://edder773.tistory.com/255