🔍 Problem

백준 2580

이 문제는 아래 그림과 같이 빈칸을 채우는 문제이다. 입력값은 한 줄씩 들어오는데 스도쿠 판의 맨 위의 줄 부터 들어온다. 공백은 0으로 나머지는 숫자 그대로 들어온다.

지금 현재 맨위의 줄은 0(공백) 3 5 4 6 9 2 7 8 이고 0에 들어갈 단어를 찾는 것이다. 그렇다면 재귀적으로 해결해야하는데 첫 번째는 트리의 노드의 기준을 뭘로 삼냐는거다. 필자의 생각은 주어진 입력에서 0의 개수로 판단하는 것이 맞는 것 같다. 시간이 지나고.. 물론 비슷했지만 결론적으로 필자는 풀지못하고 답을 봤다. 답에서 blank라는 배열에 빈공간의 좌표를 모두 넣어놓고 해당 좌표의 끝까지 즉 blank배열의 길이까지 도달했을 때 종료를 시키는 방식으로 했다. 종료시킬 때, 스도쿠의 모든 답들을 전부 출력하고 exit()로 강제종료하는 방법을 선택했다. 왜냐하면 스도쿠 답의 모든 경우의 수는 여러개고 이것을 전부 구할 필요가 없는 스페셜 저지 문제기 때문이다.

📒 해결과정

가. 해당 스도쿠의 빈 공간의 좌표를 저장해놓을 배열을 생성하고 이 공간좌표의 개수를 종료조건의 변수로 삼는다.

예를들어 빈공간이 3군데이면 len(blank) = 3 이 될 것이고, 이 한 공간씩 숫자를 넣을것이다.

나. 트리 그리기

다. Check 함수들을 선언한다.

1. check_raw(행번호, 값)
		return 행번호가 가리키는 행 안에 특정 스도쿠 값이 들어있으면 false 아니면 true
		
2. check_col(열번호, 값)
   1번과 동일

3. check_box(y,x,값)
    return 스도쿠 x,y좌표의 박스 안에 값이 존재하면 false 아니면 true
  
    ->
    for i 0 ~ 3
		    for j 0 ~ 3
					n==스도쿠[y//3*3+i][x//3*3+j] ->  return false   
    

		# 빨간색 부분
		x//3*3 = 3x3 스도쿠 한 박스의 영역의 처음 x좌표이다.
		
		# 확장 : 
		x//k*k, y//k*k = ?
		-> kxk 스도쿠 한 박스의 처음 좌표(x,y)값이다.

라. dfs 함수 작성

dfs(n:스도쿠의 n번째 빈공간): # 만약 3번째 빈공간이면 3
	
	if( n == len(빈공간 모아놓은 리스트) )
	   답 적힌 스도쿠 출력
	   강제종료
	   
	for value 1~9:
	   y = 빈공간 리스트 [n][0] # 현재 탐색중인 공간의 y좌표
	   x = 빈공간 리스트 [n][1] #      "          x좌표
	   if check_raw(y, value) and check_col(x, value) and check_box(y, z, value)
		   스도쿠[y,x] = value
		   dfs(n+1)
		   스도쿠[y,x] = 0  -> 중요, 놨던거 다시 빼줘야지 백트래킹이 된다. 이거 없는 코드도 있던데 어떻게 한거지 ;;

마. 전체 의사 코드

1. input 받고 2차원 배열로 변환
2. 빈공간 배열 얻기

3. 행 값 췍 함수
4. 열 값 췍 함수
5. 3x3 박스 값 췍 함수

6. dfs함수

7. dfs실행

---

💻 Code

import sys, os

# https://halo.oopy.io/1bbacfa8-9c47-80d9-83ab-d66f19f5ccd2
SIZE= 9
input=sys.stdin.readline
sudoku=[list(map(int,input().split())) for _ in range(SIZE)]

# mat=sys.stdin=open("Back_Tracking/ETC/input.txt","r")
# sudoku=[list(map(int,mat.readline().split())) for _ in range(SIZE)]

blank=[[i,j]for i in range(SIZE) for j in range(SIZE) if sudoku[i][j]==0]

def row_check(row, value):
    for col in range(SIZE):
        if sudoku[row][col] == value:
            return False
    return True

def col_check(col, value):
    for row in range(SIZE):
        if sudoku[row][col] == value:
            return False
    return True

def box_check(y,x,value):
    for i in range(3):
        for j in range(3):
            if sudoku[y//3*3+i][x//3*3+j] == value:
                return False
    return True

def dfs(n):
    if (n==len(blank)):
        for row in sudoku:
            for value in row:
                print(value,end=" ")
            print()
        sys.exit()
        
    for value in range(1,10):   # value : 1~9
        y=blank[n][0]
        x=blank[n][1]
        if  box_check(y,x,value) and row_check(y,value) and col_check(x, value):
            sudoku[y][x]=value
            dfs(n+1)
            sudoku[y][x]=0

dfs(0)

---

🤔 느낀점

오늘도 어김없이 굉장히 어려웠고 애먹었지만 어렵다 그래도 백트래킹할 때 어떻게 구현해야하는지도 중요하지만 3x3 검사할 때도 어려웠던 것 같다. 그럼 20000