[백준] 2580번 스도쿠

사용 언어 - PyPy3

2580번: 스도쿠 (골드4, DFS 백트래킹 문제)

문제 ★백트래킹 문제★

2580번: 스도쿠

 

 

 

정답

DFS 백트래킹 재귀함수 조합 문제 !!

다른 분들 답중에 가장 좋다고 생각하는 풀이법으로 공부했습니다. 맨 아래에 링크를 올립니다!

 

1.  전체 숫자를 모두 확인하면 재귀함수가 너무 많이 필요하기 때문에 답을 구해야하는 0인 부분만 찾는다.

zeros = [(i,j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]

 

2. zeros 안에 채워야할 promising 숫자를 찾는다.

promising 이라는 1부터 9까지의 숫자 리스트를 만든다.

 

• 행열 검사

스도쿠에서 zeros가 있는 행에 1부터 9까지의 숫자가 있다면 promising에서 remove한다.

스도쿠에서 zeros가 있는 열에 1부터 9까지의 숫자가 있다면 promising에서 remove한다.

 

• 3*3 박스 검사

1부터 9까지의 행과 열을 3으로 나눈 몫은 1,1,1,2,2,2,3,3,3이다.

zeros가 있는 행과 열을 3으로 나누어 3*3 박스로 묶어준다.

스도쿠에서 zero가 있는 3*3 박스에 1부터 9까지의 숫자가 있다면 promising에서 remove한다.

 

결론적으로, 두 검사를 끝냈을 때도 promising 리스트 안에 있는 숫자가 정답에 유력한 숫자가 된다.

 

3. dfs(x)

(i, j) = zeros[x]

정답에 유력한 숫자들을 0이 있는 곳에 넣어준다.

dfs(x+1) : zeros 인덱싱 x를 1개씩 늘려가며 재귀함수를 해준다.

정답이 만약 없다면, 0을 출력해주면서 초기화해준다.

 

모두 정답을 채워넣어서 zeros가 더이상 없다면, 답을 출력해준다.

출력형식은 리스트 형태가 아니기 때문에, 아래와 같이 각 줄을 곱해서 출력해야한다.

for row in sudoku:
    print(*row)

# 정답
sudoku = [list(map(int, input().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]

def is_promising(i, j):
    promising = [1,2,3,4,5,6,7,8,9]  

    for k in range(9):
        if sudoku[i][k] in promising:
            promising.remove(sudoku[i][k])
        if sudoku[k][j] in promising:
            promising.remove(sudoku[k][j])
            
    i //= 3
    j //= 3
    for p in range(i*3, (i+1)*3):
        for q in range(j*3, (j+1)*3):
            if sudoku[p][q] in promising:
                promising.remove(sudoku[p][q])
    
    return promising

flag = False
def dfs(x):
    global flag
    
    if flag:
        return
        
    if x == len(zeros):
        for row in sudoku:
            print(*row)
        flag = True
        return
        
    else:    
        (i, j) = zeros[x]
        promising = is_promising(i, j)
        
        for num in promising:
            sudoku[i][j] = num
            dfs(x + 1)
            sudoku[i][j] = 0
dfs(0)

 

  내가 접근한 방법도 올려본다... 오답이었다.

# 내가 접근한 방법 - 결론:오답

board = [list(map(int,input().split())) for _ in range(9)]
row_zero = [0]*9
row_cnt = 0
col_zero = [0]*9
col_cnt = 0

#가로줄 테스트해서 0이 한개이면 숫자 채워주기
def row():
    global row_cnt
    
    for i in range(9):
        for j in range(9):
            if board1[i][j] == 0:
                row_cnt += 1

        row_zero[i] = row_cnt
        row_cnt = 0
    
    return print(row_zero)

#세로줄 테스트해서 0이 한개이면 숫자 채워주기
def col():
    global col_cnt
    
    for j in range(9):
        for i in range(9):
            if board1[i][j] == 0:
                col_cnt += 1

        col_zero[j] = col_cnt
        col_cnt = 0
    
    return print(col_zero)
                            
#줄에 빈칸이 1개인 경우, 없는 숫자 넣어주기
def game():
    
    for i in range(9):
        for j in range(9):
            if row_zero[i] == 1:
                try:
                    for k in range(1,9):
                        board[i].index(k)
                except:
                    board[i][j] = k
            row()
    for j in range(9):
        for i in range(9):
            if col_zero[j] == 1:
                try:
                    for k in range(1,9):
                        board[i][j].index(k)
                except:
                    board[i][j] = k
            col()
            
            #ame()
                
    return board

 

---

레퍼런스

• 정답 참고

#309 백준 파이썬 [2580] 스도쿠 - DFS

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부