[백준] 2580번 : 스도쿠 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2580번: 스도쿠

 

1. 문제 설명

2. 풀이과정

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 빈칸에 적으려는 수가 해당 행에서 겹치지 않는지 확인하는 함수를 정의한다. def rowCheck(row, v)
3. 해당 행의 각 열의 위치를 불러오며 for c in range(9)
4. 만약 빈칸에 적으려는 수가 이미 해당 행에 동일하게 있으면 if (v == sudoku[row][c])
5. 빈칸에는 해당 수를 넣을 수 없다. return False
6. 반면, 행에서 각 열의 모든 수를 확인한 결과, 겹치는 수가 없으면 빈칸에 해당 수를 넣을 수 있다. return True
7. 빈칸에 적으려는 수가 해당 열에서 겹치지 않는지 확인하는 함수를 정의한다. def colCheck(col, v)
8. 해당 열의 각 행의 위치를 불러오며 for r in range(9)
9. 만약 빈칸에 적으려는 수가 이미 해당 열에 동일하게 있으면 if (v == sudoku[r][col])
10. 빈칸에는 해당 수를 넣을 수 없다. return False
11. 반면, 열에서 각 행의 모든 수를 확인한 결과, 겹치는 수가 없으면 빈칸에 해당 수를 넣을 수 있다. return True
12. 빈칸에 적으려는 수가 정사각형 안에서 겹치지 않는지 확인하는 함수를 정의한다. def rectCheck(row,  col, v)
13. 3x3 정사각형의 시작 행의 위치를 저장하고 rowStart = 3 * (row // 3)
14. 3x3 정사각형의 시작 열의 위치를 저장한다. colStart = 3 * (col // 3)
15. 시작 행의 위치에서 3칸씩 이동하고 for r in range(rowStart, rowStart + 3)
16. 시작 열의 위치에서 3칸씩 이동하며 for c in range(colStart, colStart + 3)
17. 만약 빈칸에 적으려는 수가 해당 3x3 정사각형 안에 동일하게 있으면 if (v == sudoku[r][c])
18. 빈칸에는 해당 수를 넣을 수 없다. return False
19. 반면, 해당 3x3 정사각형 안에 모든 수를 확인한 결과, 겹치는 수가 없으면 빈칸에 해당 수를 넣을 수 있다. return True
20. 스도쿠를 완성하는 함수를 정의한다. def dfs(idx)
21. 만약 채우려는 빈칸의 위치가 빈칸의 개수와 같아지면 if (idx == len(blank))
22. 더 이상 채울 빈칸이 없으므로 스도쿠의 각 행을 불러오고 for i in sudoku
23. 행에 따른 각 열의 값을 불러와 공백을 기준으로 한 줄에 출력한다. for j in i: print(j, end=' ')
24. 한 줄을 출력했으면 줄 바꿈을 한다. print()
25. 스도쿠를 완성했으므로 함수를 프로그램을 종료시켜 준다. exit(0)
26. 그게 아니라면 해당 빈칸에 들어갈 수 있는 숫자를 1부터 9까지 차례로 불러온다. for i in range(1, 10)
27. 빈칸의 행의 위치를 저장하고 row = blank[idx][0]
28. 빈칸의 열의 위치를 저장한다. col = blank[idx][1]
29. 만약 빈칸에 불러온 수를 넣는다고 가정하며, 각 행에서, 열에서, 3x3 정사각형에서 동일한 수가 겹치지 않는지 확인하고 모두 겹치지 않는다면 if (rowCheck(row, i) and colCheck(col, i) and rectCheck(row, col, i))
30. 해당 빈칸에 불러온 수를 넣는다. sudoku[row][col] = i
31. 해당 빈칸을 채웠으므로 다음 빈칸으로 넘어간다. dfs(idx + 1)
32. 스도쿠가 완성되지 않았다면 백트랙킹을 하며 다시 찾기 위해 다시 빈칸으로 만들어준다. sudoku[row][col] = 0
33. 스도쿠 판을 저장할 리스트를 생성하고 sudoku = list()
34. 9번 반복하며 for _ in range(9)
35. 각 행별 스도쿠 값을 입력받아 리스트로 저장한다. sudoku.append(list(map(int, sys.stdin.readline().split())))
36. 스도쿠에서 빈칸의 위치를 저장할 리스트를 생성하고 blank = list()
37. 스도쿠의 각 행과 열을 하나씩 모두 불러오며 for r in range(9): for c in range(9)
38. 만약 해당 위치가 빈칸이라면 if (sudoku[r][c] == 0)
39. 해당 위치의 행과 열의 값을 리스트로 묶어 빈칸 리스트에 추가한다. blank.append([r, c])
40. 빈칸 리스트에서 첫 빈칸의 위치를 담은 인덱스를 인수로 주어 스도쿠를 완성할 함수를 호출한다. dfs(0)

해당 코드를 Python3와 PyPy3에서 각각 실행시켜 본 결과Python3에서는 시간초과가 발생하고, PyPy3에서는 통과가 되었다.

 

반응형

3. 소스코드

import sys

def rowCheck(row, v):
    for c in range(9):
        if (v == sudoku[row][c]):
            return False
        
    return True

def colCheck(col, v):
    for r in range(9):
        if (v == sudoku[r][col]):
            return False
        
    return True

def rectCheck(row, col, v):
    rowStart = 3 * (row // 3)
    colStart = 3 * (col // 3)
    for r in range(rowStart, rowStart + 3):
        for c in range(colStart, colStart + 3):
            if (v == sudoku[r][c]):
                return False
        
    return True

def dfs(idx):
    if (idx == len(blank)):
        for i in sudoku:
            for j in i:
                print(j, end=' ')
            print()
        exit(0)

    for i in range(1, 10):
        row = blank[idx][0]
        col = blank[idx][1]

        if (rowCheck(row, i) and colCheck(col, i) and rectCheck(row, col, i)):
            sudoku[row][col] = i
            dfs(idx + 1)
            sudoku[row][col] = 0

sudoku = list()
for _ in range(9):
    sudoku.append(list(map(int, sys.stdin.readline().split())))

blank = list()
for r in range(9):
    for c in range(9):
        if (sudoku[r][c] == 0):
            blank.append([r, c])

dfs(0)