[탐색 & 시물레이션] - 스도쿠검사

스도쿠검사

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

 

나의코드 

import sys

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


ch1=[0]*10 # 가로
ch2=[0]*10 # 세로
ch3=[0]*10 # 3x3


for i in range(9):
    ch1=[0]*10 # 가로
    ch1[0]=1
    ch2=[0]*10 # 세로
    ch2[0]=1
    for j in range(9):
        ch1[arr[i][j]]+=1
        ch2[arr[j][i]]+=1

    for x in ch1:
        if x==0:
             print("No")
             sys.exit()
    for x in ch2:
        if x==0:
             print("No")
             sys.exit()

for k in range(3):
    for w in range(3):
    	ch3=[0]*10 # 3x3
        ch3[0]=1
        for i in range(3):
            for j in range(3):
                ch3[arr[i+3*k][j+3*w]]+=1
        for x in ch2:
            if x==0:
                print("No")
                sys.exit()
print("YES")

상당히 마음에 안드는 코드이다 반복문을 너무 많이 썼다..

어떻게든 구현을 하긴 했는데

ch 체크 배열을 확인하는 코드도 분명 더 개선할 수 있을 꺼같은데...흠

 

+ 3x3체크 하는 로직을 짜는데 너무 시간을 많이 썻다.. 변수 3개로 구현하려고 끙끙대다 결국 4개로 구현했는데 허허 그래도 정답 코드에서도 4개의 변수를 사용해서 구현한걸 보니 나름 잘 푼거 같다.

 

 

 

정답코드

import sys
sys.stdin=open("input.txt", "r")
def check(a):
    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")

아아 체크 배열을 +1해주는게 아닌 1로 고정을 해서 sum 함수를 사용하면 코드가 간단해 진다.