Algorithm - 스도쿠 검사

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[스도쿠 검사]

 

스도쿠는 매우 간단한 숫자 퍼즐이다.

9x9 크기의 보드가 있을 때, 각 행과 각 열 그리고 9개의 3x3 보드에 1부터 9까지 숫자를 중복 없이 채우면 된다.

스도쿠

 

위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오며, 각 3x3짜리 사각형(9개)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

완성된 9x9 크기의 스도쿠가 주어지면 정확하게 풀었으면 'YES', 잘 못풀었으면 'NO'를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 완성된 9x9 스도쿠가 주어진다.

 

*출력 설명

첫 번째 줄에 'YES' 또는 'NO'를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_20.txt', 'rt')

def check(tmp):
    for i in range(9):
        ch1 = [0] * 10
        ch2 = [0] * 10
        for j in range(9):
            ch1[a[i][j]] = 1
            ch2[a[j][i]] = 1
        if sum(ch1) != 9 or sum(ch2) != 9:
            return False
    for i in range(3):
        for j in range(3):
            ch3 = [0] * 10
            for k in range(3):
                for s in range(3):
                    ch3[a[i * 3 + k][j * 3 + s]] = 1
            if sum(ch3) != 9:
                return False
    return True

a = [list(map(int, input().split())) for _ in range(9)]

if check(a):
    print('YES')
else:
    print('No') 
    
# 출력 : YES

 

input_20.txt(입력)

1 4 3 6 2 8 5 7 9
5 7 2 1 3 9 4 6 8 
9 8 6 7 5 4 2 3 1 
3 9 1 5 4 2 7 8 6  
4 6 8 9 1 7 3 5 2  
7 2 5 8 6 3 9 1 4 
2 3 7 4 8 1 6 9 5 
6 1 9 2 7 5 8 4 3 
8 5 4 3 9 6 1 2 7

 

 

중요내용

1. ch1은 9x9 사각형의 전체 행을 탐색하는 체크리스트이고, ch2는 전체 열을 탐색하는 체크리스트이다.
2. ch1 = [0] * 10, ch2 = [0] * 10 코드는 전체 행과 열을 탐색하는 체크리스트를 0으로 초기화하는 것이다.
3. a[i * 3 + k][j * 3 + s]는 9개의 3x3 사각형의 행과 열을 탐색하는 코드이다.
4. 참고로, 9개의 3x3 사각형을 탐색하는 코드는 4중 for문으로 실행된다.