탐색&시뮬레이션(string, 1차원, 2차원 리스트 탐색 )_10_스토쿠(스도쿠) 검사

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

 

강사님 풀이

 ① 가로, 세로 맞는지 체크

 >> 가로 행을 체크하는 리스트 만들어주기 widthDetect[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 >> 세로 열을 체크하는 리스트 만들어주기 lengthDetect[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 >> 반복문 돌면서 각각의 인덱스에 해당 숫자가 있을때 1로 채워주기

      (widthDetect[a[i][j]] = 1) 또는 (lengthDetect[a[j][i]] = 1 )

 >> 다 찾았고 만약 1이 없고 2가 두번 들어있다면 lengthDetect[0, 1, 1, 1, 1, 1, 1 ,1 , 1, 1]

 >> 이런식으로 한자리가 비어서 리스트의 합이 9가 안나옴 => 틀린 스도쿠

 

 ② 3*3 그룹 체크

 >> 3*3 그룹을 체크하는 리스트 만들어주기 groupDetect[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 >> i와 j를 통해서 각각 3번씩 9번의 반복을 돌면서 그룹 9개를 순서대로 가져옴

      i와(0, 1, 2), j(0, 1, 2)만큼 반복 

      i가 0일때 j는 0, 1, 2

      i가 1일때 j는 0, 1, 2

      i가 2일때 j는 0, 1, 2

 >> k와 s도 각각 3번씩 9번을 반복하면서 그룹 안에 있는 0개의 요소를 각각의 접근

                                            a[ i*3+k ][ j*3+s ]

      i=0, j=0, k가 0이면 s는 0~2 : a[0*3+0][0*3+0]=a[0][0], a[0*3+0][0*3+1]=a[0][1], a[0*3+0][0*3+2]=a[0][2]

      i=0, j=0, k가 1이면 s는 0~2 : a[0*3+1][0*3+0]=a[1][0], a[0*3+1][0*3+1]=a[1][1], a[0*3+1][0*3+2]=a[1][2]

      i=0, j=0, k가 2이면 s는 0~2 : a[0*3+2][0*3+0]=a[2][0], a[0*3+2][0*3+1]=a[2][1], a[0*3+2][0*3+2]=a[2][2]

                         ..........

      i=1, j=0, k가 0이면 s는 0~2 : a[1*3+0][0*3+0]=a[3][0], a[1*3+0][0*3+1]=a[3][1], a[1*3+0][0*3+2]=a[3][2]

      i=1, j=0, k가 1이면 s는 0~2 : a[1*3+1][0*3+0]=a[4][0], a[1*3+1][0*3+1]=a[4][1], a[1*3+1][0*3+2]=a[4][2]

      i=1, j=0, k가 2이면 s는 0~2 : a[1*3+2][0*3+0]=a[5][0], a[1*3+2][0*3+1]=a[5][1], a[1*3+2][0*3+2]=a[5][2]

import sys
sys.stdin=open("input.txt", "r")
def check(a):
    #행, 열 체크
    for i in range(9):    
        widthDetect = [0]*10    #행 체크 리스트 생성
        lengthDetect = [0]*10    #열 체크 리스트 생성
        for j in range(9):
            widthDetect[a[i][j]] = 1    #행 체크하고 확인된 값 1채워주기
            lengthDetect[a[j][i]] = 1    #열 체크하고 확인된 값 1채워주기
            if sum(widthDetect) != 9 or sum(lengthDetect) != 9 :     #행 체크 리스크 합이 9가 아니면 false, 열 체크 리스트 합 9 아니면 false
                return False
    #3*3그룹 체크
    for i in range(3):
        for j in range(3):
            groupDetect = [0]*10    #그룹 체크 리스트 생성
            for k in range(3):      #k:0,1,2 돌면서 '3'*3탐색
                for s in range(3):  #s:0,1,2 돌면서 3*'3'탐색
                    groupDetect[a[i*3+k][j*3+s]] = 1    #i*3+k행, i*3+s열, 곱하기 해서 3의 간격만큼 커짐
            if sum(groupDetect) != 9:    #그룹 체크 리스트 합의 값이 9가 아니면 false
                return False
    return True

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