[BOJ] 2239. 스도쿠(Python) / DFS

2239번: 스도쿠

 

우리가 아는 그 스도쿠 게임이 맞다. 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하는 문제이다.

• 사용 알고리즘 : DFS
• 맵을 인풋 받으며 0의 위치를 리스트에 담는다.(zeros)
• dfs 재귀로 depth == len(zeros)가 되는 순간 완성한 맵을 형식에 맞게 출력한다.
• 기본적인 dfs함수 틀에서 빈 자리에 1부터 9까지 숫자 중 가능한 숫자를 확인한다.
  • 행 체크 : rowCheck() 함수에서 해당 행에서 같은 숫자 있으면 False, 없으면 True 리턴
  • 열 체크 : colCheck() 함수에서 해당 열에서 같은 숫자 있으면 False, 없으면 True 리턴
  • 3*3 크기 맵 체크 : squareCheck() 함수에서 해당 범위에 같은 숫자 있으면 False, 없으면 True 리턴
• 위 세 가지 조건을 모두 만족하면 해당 위치에 들어갈 수 있으므로 숫자를 그린다.
• 재귀로 depth + 1로 넘기며 계속 탐색하고, 풀려 나오면서 그렸던 숫자를 0으로 복원시킨다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline

# 행 체크
def rowCheck(r, num):
    for c in range(9):
        if board[r][c] == num:
            return False
    return True

# 열 체크
def colCheck(c, num):
    for r in range(9):
        if board[r][c] == num:
            return False
    return True

# 3 * 3 체크
def squareCheck(r, c, num):
    nr = (r//3) * 3
    nc = (c//3) * 3
    for i in range(3):
        for j in range(3):
            if board[nr+i][nc+j] == num:
                return False
    return True

def dfs(depth):
    if depth == len(zeros):
        for row in range(9):
            for col in range(9):
                print(board[row][col], end="")
            print()
        exit()
    
    nr, nc = zeros[depth]	# 현재 확인할 위치
    for num in range(1, 10):
    	# 세 가지 조건에 모두 만족하면 숫자 그리기
        if rowCheck(nr, num) and colCheck(nc, num) and squareCheck(nr, nc, num):
            board[nr][nc] = num
            dfs(depth + 1)
            board[nr][nc] = 0

# main
board = []
zeros = []		# 0의 위치 담기
for r in range(9):
    board.append(list(map(int, input().rstrip())))
    for c in range(9):
        if board[r][c] == 0:
            zeros.append((r, c))
dfs(0)

---

• 시간 : 4700ms / 메모리 : 162884kb
• 고찰 : 매우 비효율적인 코드다.. 그냥 생각나는 대로 직관 그대로 짰다ㅋㅋ 모든 빈 칸에 1~9를 넣으며 확인하며 재귀를 시전하기 때문이다,, 다음에 풀 때는 좀더 효율적인 방법을 고민해 짜봐야겠다.