[백준] 2580 스도쿠

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

빈칸에 입력이 가능한 숫자들을 채워가며 스도쿠의 조건을 만족시켜야 했습니다.

빈칸으로 주어진 좌표들을 모두 리스트로 정리하였고, 좌표들을 반복하며 해당 좌표에 입력 가능한 숫자들을 모두 구한 후 숫자들을 넣어보며 탐색하였습니다.

2) 알고리즘

• DFS
• 재귀

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def get_can_num(y, x):                              # 행, 열, 사각형을 확인해서 들어갈 수 있는 번호 구하기
    can_num = {1, 2, 3, 4, 5, 6, 7, 8, 9}.difference(sudoku[y])     # 현재 행에서 들어갈 수 있는 번호

    for j in range(9):                              # 현재 열에서 들어갈 수 있는 번호
        if sudoku[j][x] in can_num:
            can_num.remove(sudoku[j][x])

    r = y//3 * 3
    c = x//3 * 3
    for i in range(r, r+3):                         # 현재 사각형에서 들어갈 수 있는 번호
        for j in range(c, c+3):
            if sudoku[i][j] in can_num:
                can_num.remove(sudoku[i][j])
    
    return can_num

def solution(n):
    if n == N:                      # 모든 번호를 찾았다면
        for i in range(9):          # 출력
            print(*sudoku[i])
        sys.exit(0)                 # 정답 한번 찾았으면 다음 탐색하지 않고 프로그램 종료

    y, x = coor[n]                  # 빈칸의 좌표
    for num in get_can_num(y, x):   # 해당 좌표에서 들어갈 수 있는 숫자들 넣어보기
        sudoku[y][x] = num          # 숫자 입력
        solution(n+1)               # 다음 좌표 탐색
        sudoku[y][x] = 0            # 불가능한 경우, 다시 빈칸


sudoku = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]   # 주어진 입력
coor = []                                                                   # 빈칸인 좌표들

for i in range(9):
    for j in range(9):
        if not sudoku[i][j]:        # 빈칸 좌표
            coor.append((i, j))

N = len(coor)                       # 빈칸의 개수
solution(0)                         # 탐색

---

🔗 문제 링크

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

2580번: 스도쿠

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다