[BOJ] 2580 스도쿠 - python

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

풀이

빈칸을 채워야 하는 것이므로 빈 칸의 좌표를 가지고 있는 list를 만든다. 해당 빈 칸들을 돌며 가능한 후보들을 찾는다. 해당 빈 칸에 가능한 후보를 sdoku맵에 업데이트한 후 그 다음 빈 칸을 검사하러 간다. 만약 가능한 후보가 없다면 해당 route는 자동으로 종료된다. sdoku판을 다시 원상복구 시킨 후 다음 candidate를 검사한다. 마지막 zero까지 다 채워넣는 것이 성공한다면 스도쿠를 완성한 것이다.

import sys
def input():
    return sys.stdin.readline().rstrip()

sdoku = [list(map(int,input().split(" "))) for _ in range(9)]
zeros = [(i,j) for i in range(9) for j in range(9) if sdoku[i][j] == 0] #빈칸만 뽑아내기

def get_candidate(a,b):
    cand = set()
    # 가로,세로 검사
    for num in range(9):
        cand.add(sdoku[a][num]) # 가로 검사
        cand.add(sdoku[num][b]) # 세로 검사
    # block 검사
    for r in range((a // 3) * 3,(a // 3) * 3 + 3):
        for c in range((b // 3) * 3, (b // 3) * 3 + 3):
            cand.add(sdoku[r][c])
    candidate = list({1, 2, 3, 4, 5, 6, 7, 8, 9} - cand)
    return candidate

#바뀌는 것 zero, sdoku(변경, 원상복구해가며)
def dfs(zero_index):
    #종료조건
    if zero_index == len(zeros): #zero 마지막까지 완료했으면
        [print(*row) for row in sdoku] #한 줄 단위로 프린트
        sys.exit()

    #가지치기
    a,b = zeros[zero_index]
    candidate = get_candidate(a,b) #candidate가 없다면 자동으로 해당 route는 종료된다. 
    for c in candidate:
        sdoku[a][b] = c #스도쿠 판 바꿔서 전달
        dfs(zero_index+1)
        sdoku[a][b] = 0 #원상복구

dfs(0) #zero 0부터 다 돌면서 확인

얻어가는 것

• 좌표 뽑아내기

#빈칸만 뽑아내기
zeros = [(i,j) for i in range(9) for j in range(9) if sdoku[i][j] == 0] 

• 사칙연산

/ : 나누기(소숫점까지)
// : 몫
% : 나머지

• 리스트에 존재하는 수를 한 줄로 프린트하기

list = [1,2,3,4,5,6]
print(***list**)
>> 1 2 3 4 5 6

#한 줄 단위로 여러 줄 프린트
[print(*row) for row in sdoku] 

느낀점

"211110"

소요 시간 : 3h

• 오랜만에 dfs를 접해서 너무 어려웠다
• 코테 오늘부터 다시 시작,,, 빠팅빠샤,,,