[백준/Python] 2580 스도쿠

[백준/Python] 2580 스도쿠

정답 코드 및 설명

import sys
def check(row, col, sudoku):
    numbers = set(range(1, 10))  # 1부터 9까지 숫자들의 집합

    # 행과 열에서 사용된 숫자 제거
    for i in range(9):
        numbers.discard(sudoku[row][i])
        numbers.discard(sudoku[i][col])

    # 3x3 정사각형에서 사용된 숫자 제거
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            numbers.discard(sudoku[i][j])

    return numbers  # 사용 가능한 숫자들의 집합 반환

def solve_sudoku(sudoku, row=0, col=0):
    if row == 9:  # 모든 칸을 성공적으로 채웠다면 True 반환
        return True
    if col == 9:  # 한 줄의 끝에 도달했다면 다음 줄로 이동
        return solve_sudoku(sudoku, row + 1, 0)

    if sudoku[row][col] == 0:  # 빈 칸을 찾았다면
        for num in check(row, col, sudoku):
            sudoku[row][col] = num  # 숫자를 넣어본다
            if solve_sudoku(sudoku, row, col + 1):  # 다음 칸으로 이동
                return True
            sudoku[row][col] = 0  # 숫자가 맞지 않으면 0으로 되돌린다

        return False  # 빈 칸에 들어갈 수 있는 숫자가 없다면 False 반환
    else:  # 빈 칸이 아니면 다음 칸으로 이동
        return solve_sudoku(sudoku, row, col + 1)

# 스도쿠 퍼즐 입력 받기
input = sys.stdin.readline
input_sudoku = [] #스도쿠를 입력 받을 리스트

for _ in range(9):
    row = list(map(int, input().split())) #한줄씩 읽고 리스트에 삽입
    input_sudoku.append(row)

# 스도쿠 퍼즐을 풀어보자
if solve_sudoku(input_sudoku):
    for row in input_sudoku:
        print(' '.join(map(str, row)))
else:
    print("해결할 수 없는 스도쿠입니다.")

문제 요약

1. 9x9 스도쿠 판이 주어지며, 일부 칸에는 숫자가 미리 채워져있고 빈 칸은 '0' 으로 표시되어있다.

2. 빈 칸을 적절한 숫자로 채워, 완전한 스도쿠 판을 만드는 것이다.

3. 각 행, 열, 및 3x3 부분 격자에는 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.

문제 접근 방법

• 숫자 검사
  빈 칸에 들어갈 수 있는 숫자를 찾는다. 이때 해당 행, 열, 그리고 3x3 부분 격자에서 사용되지 않은 숫자만 가능하다.
• 숫자 배치
  가능한 숫자 중 하나를 선택해 빈 칸에 넣는다.
• 다음 단계로 이동
  다음 빈 칸으로 이동해 위 두 단계를 반복한다.
• 오류 시 백트래킹
  어떤 숫자도 맞지 않으면 이전 단계로 돌아가 다른 숫자를 시도한다.

코드 설명

1. check(row, col, sudoku) 함수
   이 함수는 주어진 row와 col 위치에 들어갈 수 있는 숫자들을 찾는 역할을 한다. 이를 위해 다음 단계를 수행한다:

• 1부터 9까지의 숫자들을 포함하는 집합을 생성한다.
• 해당 행(row)과 열(col)에서 이미 사용된 숫자들을 집합에서 제거한다.
• 해당 위치가 포함된 3x3 정사각형에서 이미 사용된 숫자들을 집합에서 제거한다.
• 남은 숫자들의 집합을 반환한다. 이 집합은 해당 위치에 들어갈 수 있는 숫자들을 나타낸다.

2. solve_sudoku(sudoku, row=0, col=0) 함수
   이 함수는 스도쿠 퍼즐을 해결한다. 백트래킹 알고리즘을 사용하여 다음과 같은 방식으로 작동한다:

• 먼저 row가 9에 도달했는지 확인한다. 이는 스도쿠 판의 모든 칸을 성공적으로 채웠음을 의미하며, 이 경우 True를 반환하여 함수를 종료한다.
• col이 9에 도달하면, 다음 행의 첫 번째 열로 이동한다.
• 현재 위치의 값이 0이라면 (즉, 빈 칸이라면) check 함수를 호출하여 들어갈 수 있는 숫자들을 받아온다. 각 숫자에 대해:
  • 해당 숫자를 빈 칸에 넣어본다.
  • 다음 칸으로 이동하여 solve_sudoku 함수를 재귀적으로 호출한다.
  • 만약 이후 단계에서 문제가 발생하면, 해당 숫자를 0으로 다시 초기화하고 다른 숫자를 시도한다.
• 위 과정을 반복하여 스도쿠 판을 완성한다.

3. 스도쿠 퍼즐 입력 및 해결

• 사용자로부터 스도쿠 판의 입력을 받는다. 이를 위해 9번의 반복을 통해 각 줄의 숫자를 읽어 리스트에 저장한다.
• solve_sudoku 함수를 호출하여 스도쿠 퍼즐을 해결한다.