[백준/파이썬][Gold IV] 스도쿠 - 2239

[Gold IV] 스도쿠 - 2239

문제 링크

성능 요약

메모리: 142488 KB, 시간: 5592 ms

분류

백트래킹, 구현

제출 일자

2024년 12월 19일 22:55:24

문제 설명

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

풀이

def is_valid(num, row, col) :
    # 1. 현재 위치에 num이 들어갈 수 있는지 검사
    return not(in_row(num, row) or in_col(num, col) or in_box(num, row, col))

def in_row(num, row) :
    # 2. 해당 행에 num이 있는지 확인
    return num in arr[row]

def in_col(num, col) :
    # 3. 해당 열에 num이 있는지 확인
    return num in (arr[i][col] for i in range(9))

def in_box(num, row, col) :
    # 4. 현재 위치에 3x3 박스에 num이 있는지 확인
    box_row = (row // 3) * 3
    box_col = (col // 3) * 3

    for i in range(box_row, box_row + 3) :
        for j in range(box_col, box_col + 3) :
            if arr[i][j] == num :
                return True

    return False

def find_empty_position() :
    # 5. 스도쿠 보드에 비어있는 위치 반환
    for i in range(9) :
        for j in range(9) :
            if arr[i][j] == 0 :
                return i, j

    return None
def solve() :
    # 6. 비어 있는 위치에 가능한 숫자를 넣어가며 스도쿠 해결
    empty_pos = find_empty_position()
    # 7. 빈 칸이 없으면 스도쿠가 해결된 것으로 간주
    if not empty_pos :
        return True
    row, col = empty_pos
    for num in range(1, 10) :
        if is_valid(num, row, col) :
            arr[row][col] = num
            if solve() :    # 8. 다음 빈 칸으로 재귀적으로 탐색
                return True
            arr[row][col] = 0   # 9. 가능한 숫자가 없으면 원래의 0으로 되돌림

    return False
arr = [list(map(int, input())) for _ in range(9)]
solve()
for i in arr :
    print(*i, sep='')

 

1. is_valid(num, row, col)

def is_valid(num, row, col) :
    # 1. 현재 위치에 num이 들어갈 수 있는지 검사
    return not(in_row(num, row) or in_col(num, col) or in_box(num, row, col))

• 주어진 숫자 num이 (row, col) 위치에 들어갈 수 있는지 판단합니다.
• 조건:
  1. 행에 num이 없어야 함.
  2. 열에 num이 없어야 함.
  3. 해당 위치의 3x3 박스에 num이 없어야 함.
• 이 함수는 세 가지 검사를 in_row, in_col, in_box로 위임합니다.

---

2. in_row(num, row)

def in_row(num, row) :
    # 2. 해당 행에 num이 있는지 확인
    return num in arr[row]

• 특정 숫자 num이 해당 행에 있는지 확인합니다.
• 사용한 방법:
  • num in arr[row]: row 행의 리스트에서 num을 찾습니다.

---

3. in_col(num, col)

def in_col(num, col) :
    # 3. 해당 열에 num이 있는지 확인
    return num in (arr[i][col] for i in range(9))

• 특정 숫자 num이 해당 열에 있는지 확인합니다.
• 사용한 방법:
  • 열 col의 숫자들을 리스트 컴프리헨션을 이용해 생성하고, 그 안에 num이 있는지 확인합니다:

---

4. in_box(num, row, col)

def in_box(num, row, col) :
    # 4. 현재 위치에 3x3 박스에 num이 있는지 확인
    box_row = (row // 3) * 3
    box_col = (col // 3) * 3

    for i in range(box_row, box_row + 3) :
        for j in range(box_col, box_col + 3) :
            if arr[i][j] == num :
                return True

    return False

• 숫자 num이 (row, col)이 속한 3x3 박스 안에 있는지 확인합니다.
• 3x3 박스의 시작 위치를 계산:
• 3x3 박스의 범위를 탐색하면서 num이 있는지 확인:
   

---

5. find_empty_position()

def find_empty_position() :
    # 5. 스도쿠 보드에 비어있는 위치 반환
    for i in range(9) :
        for j in range(9) :
            if arr[i][j] == 0 :
                return i, j

    return None

• 스도쿠 보드에서 아직 채워지지 않은 첫 번째 빈 칸(값이 0)을 반환합니다.
• 반환값:
  • 빈 칸이 있다면 (row, col) 좌표를 반환.
  • 빈 칸이 없다면 None 반환.

---

6. solve()

def solve() :
    # 6. 비어 있는 위치에 가능한 숫자를 넣어가며 스도쿠 해결
    empty_pos = find_empty_position()
    # 7. 빈 칸이 없으면 스도쿠가 해결된 것으로 간주
    if not empty_pos :
        return True
    row, col = empty_pos
    for num in range(1, 10) :
        if is_valid(num, row, col) :
            arr[row][col] = num
            if solve() :    # 8. 다음 빈 칸으로 재귀적으로 탐색
                return True
            arr[row][col] = 0   # 9. 가능한 숫자가 없으면 원래의 0으로 되돌림

    return False

• 재귀적 백트래킹 알고리즘을 이용해 스도쿠를 풉니다.
• 주요 논리:
  1. 빈 칸을 찾음: find_empty_position().
  2. 빈 칸이 없으면: 스도쿠가 해결됨 → True 반환.
  3. 빈 칸이 있다면: 1~9까지 가능한 숫자를 하나씩 시도.
  4. is_valid(num, row, col)로 현재 숫자가 유효한지 확인.
  5. 유효하다면:
     • arr[row][col] = num으로 숫자를 배치.
     • 다음 빈 칸을 재귀적으로 탐색: solve().
  6. 재귀 호출이 실패하면(해결 불가), 배치한 숫자를 원상태로 복원: arr[row][col] = 0.
  7. 가능한 숫자를 모두 시도해도 해결되지 않으면 False 반환.

---

7. 입력 및 출력

1. • 9개의 줄에 걸쳐 스도쿠 보드의 초기 상태가 주어집니다. 각 줄은 0~9 사이의 숫자 9개로 구성됩니다. 0은 빈 칸을 나타냅니다.입력:
2. • 해결된 스도쿠 보드를 출력합니다.출력:

---

8. 백트래킹 알고리즘의 작동 방식

• 이 코드의 핵심은 백트래킹입니다.
• 스도쿠 보드를 탐색하면서 가능한 숫자를 배치하고, 잘못된 경로라면 되돌아가 다른 숫자를 시도합니다.
• 재귀적으로 모든 가능한 조합을 탐색하므로 완전탐색과 유사합니다.

---

9. 효율성

• 시간 복잡도: 최악의 경우 O(9^81), 모든 빈 칸에 대해 9가지 숫자를 시도.
• 실제로는 백트래킹이 가지치기를 하기 때문에 효율적입니다.

 

예전에 푼 기억이 있어서 풀어볼려고 했는데 생각이 도저히 나질 않았다. 백트래킹은 계속 연습해도 어렵다. 

다음에는 안 보고 풀어보도록 해야겠다.