스도쿠 검사

스도쿠 검사

스도쿠는 매우 간단한 숫자 퍼즐이다. 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

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

YES

---

코드1

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

def check(arr):
    for i in range(9):
        a = [] # 행
        b = [] # 열
        for j in range(9):
            a.append(arr[i][j])
            b.append(arr[j][i])
        a.sort()
        b.sort()
        if a!=b:
            return False

    for i in range(3):
        for j in range(3):
            c = [] # 3x3 사각형
            for k in range(3):
                for s in range(3):
                    c.append(arr[i*3+k][j*3+s])
            c.sort()
            if c!=a:
                return False
    return True

if check(arr):
    print("YES")
else:
    print("NO")

 

매번 행과 열을 탐색할 때마다, 비교하기 위해 새로운 리스트를 만들어주므로,

for문 안에다가 새로운 리스트를 선언해야 한다. (밖에다가 해서 append 하면 리스트가 계속 쌓임)

 

새로운 리스트를 sort하여 비교한 후 일치하지 않으면 False를 리턴해주는 방식으로 비교했다.

 

3x3 사각형을 탐색하는 방법에서 조금 오래 걸렸다.

3x3 사각형을 탐색하는 방법은 3칸씩 for문을 돈 다음, 그만큼 3칸씩 또 for문을 돌아주면 된다.

 

비교할 때 sort() 함수를 써서 비교하므로 시간 복잡도가 더 늘어났을 것이다.

---

코드2

def check(a):
    for i in range(9):
        ch1 = [0]*10 # 행 체크
        ch2 = [0]*10 # 열 체크
        for j in range(9):
            ch1[a[i][j]]=1 # 행 : 해당 인덱스에 1 삽입
            ch2[a[j][i]]=1 # 열 : 해당 인덱스에 1 삽입
        if sum(ch1)!=9 or sum(ch2)!=9: # 합이 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

arr = [list(map(int, input().split())) for _ in range(9)]
if check(arr):
    print("YES")
else:
    print("NO")

 

리스트를 0으로 채운 다음

행과 열 안의 숫자를, 0으로 채운 리스트의 인덱스로 하여, 1을 삽입하는 방법이 있다.

그리고 삽입된 리스트의 합을 구해서 9가 아니면 리스트가 다 채워지지 않은 것이므로 False를 리턴해주면 된다.

 

 

TypeError: 'int' object is not subscriptable

변수에 리스트를 전달하는데, 어떤 변수가 int로 받아진 곳이 있었다.