[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-10 "스도쿠 검사"

스도쿠 검사

 

[시간복잡도]

O(N⁴) = for 문을 4개 사용함.

[공간복잡도]

O(N²) = 어차피 체크하는 변수들은 9x9개의 이차원 배열의 형태이기 때문에

 

 

Problem

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

 

 

위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오 고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색 깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다. 완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES", 잘 못 풀었으면 ”NO"를 출 력하는 프로그램을 작성하세요.

 

▣ 입력설명

 

첫 번째 줄에 완성된 9×9 스도쿠가 주어집니다.

 

▣ 출력설명

 

첫째 줄에 “YES" 또는 ”NO"를 출력하세요.

 

▣ 입력예제

 

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

 

▣ 출력예제

 

YES

 

 

 

 

💯 Solution ①

: 20분동안 문제를 풀어봤지만, 행열에 대해서는 접근할 수 있었지만,

"3X3 박스"를 체크하는 방법을 생각하지 못해서 튜터님의 코드를 참고했다.

 

(총 코드)

import sys
sys.stdin=open("input.txt","rt")
 
def check(a):
    for i in range(9):
        check_rows = [0] * 10
        check_cols = [0] * 10
        for j in range(9):
           check_rows[a[j][i]]=1
          check_cols[a[i][j]]=1
        # 행이나 열에 1~9까지에서 하나씩 가지지 않는 경우
        if sum(check_rows) != 9 or sum(check_cols) != 9:
            return False
 
    for i in range(3):
        for j in range(3):
            check_boxs = [0] * 10
            for k in range(3):
                for s in range(3):
                    check_boxs[a[i*3+k][j*3+s]]=1
            if sum(check_boxs) != 9:
                return False
    return True
 
a=[list(map(int,input().split())) for _ in range(9)]
 
if check(a):
    print("YES")
else:
    print("NO")

- check(a) 라는 함수를 만든다. 이 함수는 1~9까지의 값이 행과열 그리고 3x3에 있는지 확인하는 함수이다.

 

- 이중 for문을 통해서 이차원 배열에 접근하고, a[i][j]를 통해서 하나씩 접근하면서 있다면 빈 배열로 만든 check_rows 와 check_cols의 인덱스값에 1로 변경한다. (i가 돌때마다 check_rows 와 check_cols 는 초기화된다.)

- 1로 변경하고서, 총합이 만약 9가 아니라면 (1~9까지 다 있다면 모든 인덱스에 1이 있어야하고 다 더하면 9가 되어야함.) 1~9까지 모든 수가 있는 것이 아니기 때문에 retrun False 를 한다.

 

    for i in range(9):
        check_rows = [0] * 10
        check_cols = [0] * 10
        for j in range(9):
           check_rows[a[j][i]]=1
           check_cols[a[i][j]]=1
        # 행이나 열에 1~9까지에서 하나씩 가지지 않는 경우
        if sum(check_rows) != 9 or sum(check_cols) != 9:
            return False

=> i를 고정하고 j를 0~8까지 반복한다.

 

(i,j) = (0,0), (0,1), (0,2) ...... (0,8)  (x축 고정, y값만 바뀜)

(j,i) = (0,0), (1,0), (2,0) ........ (8,0) (x값만 바뀜, y축은 고정)

 

이를 통해서, 행과 열을 분석한다.

 

 

그리고, 이제 3x3 칸을 분석해야한다.

 

    for i in range(3):
        for j in range(3):
            check_boxs = [0] * 10
            for k in range(3):
                for s in range(3):
                    check_boxs[a[i*3+k][j*3+s]]=1
            if sum(check_boxs) != 9:
                return False

여기에서 i와 j를 통해서 그룹 9개를 순서대로 가져올 수 있게 한다.

그리고 k와 s를 통해서 그룹 안에 있는 9개의 요소에 접근할 수 있다.

 

이렇게 하나의 그룹에 그룹 안에 있는 요소들을 접근하면서 1~9까지의 값이 있다면 해당 인덱스의 값에 1을 정의하고, 이 리스트(check_boxs)에 총합이 9가 아니라면, 1~9까지의 값 중에서 하나라도 없다는 것이기 때문에 False 를 반환한다.

 

만약, 모든 for문을 정상적으로 돌게 되면, True를 반환한다.

 

마지막으로,

 

- 한 줄의 리스트를 받아오는 과정을 9번 반복하는 것을 a에 담는다.

- 만약 a를 check() 함수에 담은 check(a)가 True라면, "YES"를 출력하고, False라면, "NO"를 출력한다.

 

 

 

 

💯 Solution ②

: Tutor's Code

 

import sys
sys.stdin=open("input.txt","rt")
 
def check(a):
    for i in range(9):
        check_rows = [0] * 10
        check_cols = [0] * 10
        for j in range(9):
            check_rows[a[i][j]]=1
            check_cols[a[i][j]]=1
        # 행이나 열에 1~9까지에서 하나씩 가지지 않는 경우
        if sum(check_rows) != 9 or sum(check_cols) != 9:
            return False
 
    for i in range(3):
        for j in range(3):
            check_boxs = [0] * 10
            for k in range(3):
                for s in range(3):
                    check_boxs[a[i*3+k][j*3+s]]=1
            if sum(check_boxs) != 9:
                return False
    return True
 
a=[list(map(int,input().split())) for _ in range(9)]
 
if check(a):
    print("YES")
else:
    print("NO")

 

📚 참고

 

 

⚙️저장소

github.com/JiHoon-JK/Algorithm/blob/main/inflearn/python/%EC%84%B9%EC%85%983-10.py

JiHoon-JK/Algorithm