Baekjoon 2580번. 스도쿠

2023.02.12.(일)

문제

백트래킹과 깨달음

재귀함수 및 그와 관련된 알고리즘을 이해하는 것이 그동안 너무 어려웠습니다. 사실 시간이 지난 지금도 원리를 정확히 이해했다고 보기는 어려워요. 물론 다른 알고리즘도 마찬가지이긴 하다만, 재귀함수 부분이 저한테는 유난히 어렵게 느껴집니다.

처음에 백트래킹 알고리즘을 접했을 때는, 도대체 이게 무슨 말인가… 문제를 풀려고 해도, 처음에 어디서부터 어떻게 코드를 짜야할지 감이 전혀 오지 않았습니다. 어쩔 수 없이 제가 이해한 대로 문제를 차근차근 풀어나가는 방식이 아니라 강의를 보고 다른 사람의 풀이를 여러 번 보고, 또 외우고를 반복했습니다. 그러고 시간이 조금 지난 요즈음, 문제를 어떻게 풀어야할 지 감이 슬슬 오는 듯 합니다.

이건 이렇게 풀면 되지 않을까? 저건 저렇게 풀어볼까? 문제풀이의 방식과 알고리즘의 구조가 머릿속에 정확히 그려지지는 않지만, 문제를 어떻게 풀어야 할지를 아는 느낌… 손에 잡히는 느낌이랄까요?? 백트래킹 문제를 풀 때 지켜야 하는 규칙과 형식을 무의식적으로 익힌 느낌입니다.

일단 base case(종료 조건)이 있어야 하구요, 반복문이나 함수를 재실행시킬 조건과 순서, 그리고 조건을 되돌리는 작업 등등이 있어야함을 제가 본능적으로 알고 있는 것 같아요. 정말 신기하더군요. 머릿속에 관련 데이터를 계속 넣다보면, 무언가 윤곽이 잡히긴 하는구나. 원하는 바를 위해 열심히 노력하고 관련 지식을 머릿속에 많이 집어 넣다보면 언젠가 되는 날이 오겠구나, 천재가 아니어도 되는구나, 라는 생각이 들었습니다.

백준에는 N과 M 백트래킹 시리즈 문제들이 있습니다. 이 문제들이 술술 풀리더군요. 얼마전까지만 해도 이 문제들을 보기만 해도 머릿속이 하얘졌는데 말입니다.

이번에는 조금 더 어려운 문제, 골드 4 스도쿠 문제에 바로 도전해 봤습니다. 글을 쭉쭉 써내려 나가듯이, 코드가 술술 써졌습니다.

어?? 이거 바로 통과하겠는데??

기대를 해보았으나… 여러번의 [틀렸습니다]를 맛보아야 했습니다. 반례가 조금 있더라구요.

반례들을 통해서 제 코드를 다듬고 또 다듬고 드디어 예제와 반례들에 대하여 통과할 수 있도록 만들었습니다.

하지만 또 한 번의 고비… 이번에는 [시간초과]가 납니다. 재귀 함수에 다중 for 문이 있어서 그런 것 같아요. 어떻게 해야 시간을 줄일 수 있을지를 고민해 보는 것이 또 하나의 과제가 될 것 같습니다.

일단 제가 문제에 어떻게 접근했는지를 보여드릴게요!

접근 방법

글을 쓸 때에 초안을 작성하듯이, 아래 사진들은 제가 작성한 의사 코드입니다. 직접 코드를 작성할 때는, 여기에 살을 더욱 붙여 통과되지 않는 테스트 케이스들은 없는지 계속해서 검증을 해가면서 다듬게 됩니다.

재귀함수를 사용했고 백트래킹 알고리즘을 잘 적용했다고 여겨지기는 하나, 문제는 시간초과가 발생한다는 점입니다. 어떻게 해야 제 알고리즘이 문제를 빠르게 풀어낼 수 있을까요? 아마도 다른 사람들의 의견과 풀이법을 참고해야할 듯 싶습니다.

시간이 갈수록 제 스스로가 성장하고 있는 것이 느껴집니다.

코드

board = [  list(map(int, input().split()))  for _ in range(9)  ] # 스도쿠 보드판에 숫자 입력 받기. 
voidBoard = []
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            voidBoard.append([i,j])


def backtrack(count, nextNum):

    if count == len(voidBoard):
        # TODO (결과 출력)
        done = 0
        for i in board:
            for j in i:
                print(j, end = ' ')
            print()
        exit(0)
    

    for num in range(1, 10):

        #for j in board:
            #for i in j:
                #print(i, end = " ")
            #print()
            
        if num <= nextNum: continue
        if count >= len(voidBoard): return

        #가로축
        for col in range(9):
        # 만약에 가로축에 num이 이미 있다면, return. 더이상 진행할 수 없음.
            if col == voidBoard[count][1]: continue
            if board[voidBoard[count][0]][col] == num:
                board[voidBoard[count][0]][voidBoard[count][1]] = 0
                backtrack(count, nextNum + 1)
                return
            
        #세로축
        for row in range(9):
        #만약에 세로축에 num이 이미 있다면, return. 더이상 진행할 수 없음.
            if row == voidBoard[count][0]: continue
            if board[row][voidBoard[count][1]] == num:
                board[voidBoard[count][0]][voidBoard[count][1]] = 0
                backtrack(count, nextNum + 1)
                return
        

        #네모 한 칸에 대하여.
        if voidBoard[count][0] < 3: row = 0
        elif voidBoard[count][0] < 6: row = 3
        elif voidBoard[count][0] < 9: row = 6
        if voidBoard[count][1] < 3: col = 0
        elif voidBoard[count][1] < 6: col = 3
        elif voidBoard[count][1] < 9: col = 6

        for i in range(row, row+3):
            for j in range(col, col+3):
                #만약 네모 한 칸에 num이 이미 있다면, return. 더이상 진행할 수 없음.
                if voidBoard[count][0] == i and voidBoard[count][1] == j: continue
                if board[i][j] == num:
                    board[voidBoard[count][0]][voidBoard[count][1]] = 0
                    backtrack(count, nextNum+1)
                    return

        #print("count: ", count)
        # 먼저 빈칸에 숫자를 넣어보자.
        
        board[voidBoard[count][0]][voidBoard[count][1]] = num
        backtrack(count+1, 0)
        board[voidBoard[count][0]][voidBoard[count][1]] = 0
    
backtrack(0, 0)