[백준] 2580: 스도쿠

이번 문제는 백준 난이도 골드4인 '스도쿠' 문제이다.

 

우선 문제에 대해 먼저 설명을 하면 우리가 흔히 아는 스도쿠의 개념을 그대로 프로그래밍에 적용하는 건데

직접 좌표를 입력해서 좌표 내에 숫자가 0인 좌표가 빈칸이라고 생각하면 된다.

 

문제를 풀기 전에 스도쿠의 조건을 한번 정리해보자면

• 가로줄에 중복되는 숫자가 없어야 한다.
• 세로줄에 중복되는 숫자가 없어야 한다.
• 3x3 크기의 보드에 중복되는 숫자가 없어야 한다. 

→ 위 조건을 만족하면서 1~9까지의 숫자를 채우면 된다.

 

 

 

 

---

[Python]

 

일단 직관적으로 생각해서 접근해보게 되면.

스도쿠의 전체 보드를 탐색하면서 0인 좌표를 찾고, 해당 좌표에 1~9까지 숫자를 대입해보며 넣을 수 있는 숫자를 찾으면 된다.

 

그럼 지금 내가 말한 방식으로라면

for x for문으로 전체 맵에서 0좌표를 찾기 위해 O(n²)의 시간이 걸린다. 

for r in range(9):
	for c in range(9):
    	if maps[r][c] == 0:
        	# 0인지 확인

위와 같은 형태

 

그렇다면 0을 찾았을 때는?

다시 1~9까지의 숫자를 하나씩 대입해보며 위에 말했던 스도쿠의 3가지 조건에 부합하는지 각각 확인을 해봐야한다.

여기서 for문 하나가 더 추가됨으로써 시간복잡도는 O(n³)의 시간이 된다. 

for r in range(9):
	for c in range(9):
    	if maps[r][c] == 0:
        	# 0인지 확인
            for num in range(1, 10):
            	# if 조건 : 가로줄, 세로줄, 3x3 보드 내 숫자가 있는지
                maps[r][c] = num

 

이 접근법은 효율성 문제도 있지만, 더 치명적인 논리적 오류를 가지고 있다.

바로 한 번 내린 선택을 되돌릴 수 없다는 점이다.

만약 어떤 빈칸에 가능한 첫 번째 숫자를 넣었는데, 그 선택 때문에 나중에 다른 빈칸을 아예 채울 수 없는 막다른 길에 도달하면?

이 코드는 이전에 했던 선택을 수정할 방법이 없으므로 결국 틀린 답을 내거나 스도쿠를 완성하지 못한 채 끝나버린다.

 

 

 

그래서 우리는 빈칸을 하나씩 채워나가면서 막히는 경우에 (빈칸을 1~9로 채울 수 없는 경우) 다시 되돌아가 이전 빈칸을 수정하는

방식으로 진행해야 한다.

 

 

이러한 탐색전략을 '백트래킹'이라고 부른다.

백트래킹은 재귀함수를 통하여 탐색과 후퇴 과정을 구현한다.

 

dfs를 재귀적으로 구현해 각 빈칸에 1~9까지의 숫자를 채워보며 최종숫자를 찾아나가면 된다.

 

우선 문제의 입력을 받아 스도쿠 보드를 생성한다.

import sys
input = sys.stdin.readline

N = 9

maps = [list(map(int, input().split())) for _ in range(N)]

 

보드를 생성한 뒤, 처음에 말한 방식대로 바로 탐색을 하게 되면 시간복잡도의 효율이 너무 떨어진다.

 

그래서 탐색 전에 미리 보드에서 0의 좌표들을 찾아줄 것이다.

0인 좌표들을 따로 저장해두고,

0이 아닌 좌표들은 T/F로 구분하여 표시를 해준다.

col_check = [[False] * 10 for _ in range(N)]
row_check = [[False] * 10 for _ in range(N)]
box_check = [[False] * 10 for _ in range(N)]

 

가로줄, 세로줄, 3x3 박스 각각에 대해 숫자(1~9)의 사용 여부를 기록할 3개의 체크리스트를 생성한다.

예를 들어 row_check[행][숫자]의 값이 True라면, 해당 '행'에 해당 '숫자'가 이미 사용 중이라는 의미이다.

반대로 False는 아직 해당 줄에 그 숫자가 없어서 사용 가능하다는 의미이다.

 

*10을 한 이유는 인덱스와 숫자값을 맞추기 위함 (0~8이 아닌 0~9까지 생성해서 0은 안쓰는 인덱스!)

 

zeros = []

for row in range(N):
	for col in range(N):
    	if maps[row][col] == 0:
        	zeros.append((row, col))
        else:
        	num = maps[row][col]
            box_idx = (r//3) * 3 + (c//3)
            row_check[row][num] = True
            col_check[col][num] = True
            box_check[box_idx][num] = True
            
zeros_length = len(zeros)

 

0인 좌표를 저장하기 위한 zeros 리스트도 생성해준다.

이제 maps의 모든 좌표를 돌면서 값이 0인 보드의 좌표를 저장해준다. (행, 열) 튜플로 저장

그 외에는 해당 위치의 숫자를 이용해 check 리스트들에 해당 숫자를 사용중이라고 표시한다(True)

False는 1~9중 아직 사용되지 않은 숫자라는 의미다.

 

중간에 box_idx = (r//3) * 3 + (c//3) 부분에 대한 설명은

박스의 위치를 참고하는 인덱스인데, 9x9를 기준으로 3x3 보드는 위와 같이 9구역으로 나눌 수가 있다.

전체 보드의 인덱스는 0~8까지이다. 행/열 모두 포함.

 

그렇다면 행인        r을 // 3 했을 때의 몫은 0~2 = 0, 3~5 = 1, 6~8 = 2가 되고,

마찬가지로 열인    c를 // 3 했을 때의 몫은 0~2 = 0, 3~5 = 1, 6~8 = 2가 된다.

곱하기 3을 하는 이유는

우리가 r // 3를 통해 구한 몫에 곱해줌으로써 박스 번호를 맞춰주기 위함이다.

 

쉽게 예시를 들자면, r = 3, c = 1인 (3,1)의 좌표가 위치한 박스 번호를 찾고자 할때

(3 // 3) * 3 + (1 // 3) = 1*3+0 = 3 → 3번 박스에 위치함을 알 수 있다.

(4, 7)좌표의 박스 번호는? → (4//3) * 3 + (7//3) = 1*3+2 = 5번 박스이다.

 

 

* 이 부분이 많이 헷갈릴 수 있는 부분이다.

row_check[row][num] = True
col_check[col][num] = True
box_check[box_idx][num] = True

이 코드의 의미는

row_check[1][num]은 1행에 num이라는 숫자가 있다고 True로 표시하는 것이다.

col은 열에 num이라는 숫자가 있다는 걸 표시하는 것이고

box는 몇번째 박스에 num이라는 숫자가 있는지 표시하는 것이다.

 

헷갈릴 수 있는 부분은

for row in range(N):
	for col in range(N):

 

이 초기화 코드는 보드를 (0,0)부터 (8,8)까지 순서대로 스캔한다.

하지만 보드에 적힌 숫자 자체는 문제에 따라 뒤죽박죽일 것이다.

하지만 모든 칸을 빠짐없이 확인하기 때문에, 이 과정이 모두 끝나면 3개의 check 리스트는 스도쿠 판의 초기 숫자 분포를

반영한 '상태 맵'이 된다. 이제 백트래킹은 이 맵을 보고 빈칸을 채워나갈 준비를 마친다!!

→ 체크리스트를 통해 해당 열, 행, 박스에 어떤 숫자가 있는지 바로 찾을 수 있다는 것.!

이 체크리스트를 생성하게 되어 우리는 O(n)의 시간을 O(1)의 시간으로 단축시킬 수 있다. ([행,열,박스][num]으로 T/F 반환)

 

 

 

이제 체크리스트까지 작성을 했으니 본격적으로 빈칸을 채워나갈 차례다.

빈칸을 채우는 건 dfs를 통해 구현한다.

def dfs(index):
    if index == zeros_length:
    	for i in range(N):
        	print(*maps[i])
        sys.exit(0)
        
    r, c = zeros[index]
    box_idx = (r//3) * 3 + (c//3)
    
    for num in range(1, 10):
    	if not col_check[c][num] and not row_check[r][num] and not box_check[box_idx][num]:
            maps[r][c] = num
            
            col_check[c][num] = True
            row_check[r][num] = True
            box_check[box_idx][num] = True
            
            dfs(index+1)
            
            col_check[c][num] = False
            row_check[r][num] = False
            box_check[box_idx][num] = False
  
  dfs(0)

 

말했듯이 dfs는 재귀적으로 호출해 백트래킹을 구현한다.

이 dfs 함수는 빈칸을 채우는 숫자를 찾는 역할을 하는 함수이다.

재귀의 종료 조건으로 index가 0의 좌표가 들어있는 zeros의 크기와 같아지면 종료하고 모두 채운 스도쿠 맵을 출력한다.

 

조건에 해당하지 않으면 r, c에 0점 좌표를 저장한다. zeros는 0,0부터 순서대로 0점의 좌표가 저장되어 있기 때문에 가장 처음

인덱스부터 접근하여 사용한다.

 

위 if 조건문은 col_check, row_check, box_check 세 리스트를 모두 조회해서, 지금 넣으려는 num에 대한 기록이 세 군데 모두

없는가(모두 False인가)?를 판단하는 조건식이다.

 

즉, 이 자리에 num을 놓아도 스도쿠 규칙에 위배되지 않고 안전한가?를 O(1) 시간에 확인하는 것이다!

이 검사를 통과해야만 빈칸에 숫자를 채우는 다음 단계로 넘어갈 수 있다.

 

 

그런 다 스도쿠 맵에 해당 num을 저장하고 체크리스트에 해당 num을 사용중이라고 True로 상태 변경한다.

 

그 후, dfs(index + 1)을 호출해 현재 인덱스의 다음 인덱스, 즉 다음 0점 좌표에 들어갈 숫자를 찾는다.

 

이렇게 쭉쭉쭉쭉 재귀적으로 호출을 하다가, 어느 빈칸에서 1~9숫자 중 아무것도 위 조건에 해당하지 않아 

dfs가 아무 반환값 없이 종료되게 되면 (하위 dfs함수)

 

다시 그 이전 인덱스의 dfs로 (상위 dfs함수) 돌아가 체크리스트를 False로 수정한다. (원상복구)

→ 이 뜻은 해당 num으로는 스도쿠를 채울 수 없다는 걸 의미함. 다른 숫자 시도하게 됨

 

이렇게 계속 진행하다가 종료 조건을 만나면 스도쿠가 완성된다.

 

[전체 코드]

import sys
input = sys.stdin.readline

N = 9

maps = [list(map(int, input().split())) for _ in range(N)]

col_check = [[False] * 10 for _ in range(N)]
row_check = [[False] * 10 for _ in range(N)]
box_check = [[False] * 10 for _ in range(N)]

zeros = []


for row in range(N):
    for col in range(N):
        if maps[row][col] == 0:
            zeros.append((row, col))
        else:
            num = maps[row][col]
            box_idx = (row//3) * 3 + (col//3)
            col_check[col][num] = True
            row_check[row][num] = True
            box_check[box_idx][num] = True
            
len_zeros = len(zeros)

def dfs(index):
    if index == len_zeros:
        for i in range(N):
            print(*maps[i])
        sys.exit(0)
    
    r, c = zeros[index]
    box_idx = (r//3) * 3 + (c//3)

    for num in range(1, 10):
        if not col_check[c][num] and not row_check[r][num] and not box_check[box_idx][num]: 
            maps[r][c] = num          

            col_check[c][num] = True  
            box_check[box_idx][num] = True    
            row_check[r][num] = True  

            dfs(index+1)              

            col_check[c][num] = False     
            row_check[r][num] = False      
            box_check[box_idx][num] = False    


dfs(0)