탐색 & 시뮬레이션 [수토쿠 검사] (죽음의 4중 포문...)

코테 연습을 위해 알고리즘 복습을 하며 탐색의 기본격이라 할 수 있는 수토쿠 검사 

 

알고리즘을 풀어보았다. 구간 검사를 위해 4중 포문을 돌려야하는 번거로움이 있지만,

 

알고리즘 자체는 그리 어렵지 않다. 

 

 

 

 

 

3가지에 대한 검사를 해야한다. 

 

1) 가로행에 1 ~ 9 가 다 있는지,

2) 세로행에 1 ~ 9 가 다 있는지,

3) 3*3 총 9개의 구간에 1 ~ 9 가 다 있는지,

 

먼저 9*9 총 81개의 숫자를 리스트(sudo) 에 담아준다. 

 

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

 

그 뒤 check 라는 검사 함수를 만들어준다. 

 

check 함수 안에는 1) 2) 3)을 차례로 검사해주는데 만약 거짓이 있는 순간 바로 False를 return

 

하도록 해준다.

 

검사는 1) 2) 3) 각 항목을 check_lst1, check_lst2, check_lst3 의 인덱스를 0->1 로 바꿔주면서

 

체크해나간다. 1) 2)는 이중 포문을 통해 각각 행과 열에 따라 인덱스 값을 바꿔주고 최종적으로

 

그 바꿔준 인덱스의 총 합이 9이면 1 ~ 9 모든 수가 다 존재하는 것으로 볼 수 있다.

 

3) 구간 검사가 살짝 문제인데, 처음에 획기적인 방법이 있을 거라 생각했는데, 문제 풀이 강의를

 

들으니 그냥 4중 포문 노가다 작업이었다.

 

i와 j를 통해 9개의 구간을 잡아주고 각각의 3*3 판을 또 이중 for문과 check_lst3의 인덱스를 통해

 

1), 2) 와 동일한 방법으로 체크해주면 된다.

 

체크가 끝나고(1)2)3) 모든 경우를 통과했을 때) 함수는 True를 return 해주면 된다.

 

import sys

#sys.stdin=open("input.txt", 'rt')

def check(lst):

    check_lst2 = check_lst3 = [0]*10

    for i in range(9): # check_lst1 => 행 체크   check_lst2 => 열 체크

        check_lst1 = [0]*10

        check_lst2 = [0]*10

        for j in range(9):

            check_lst1[lst[i][j]] = 1

            check_lst2[lst[j][i]] = 1

        if sum(check_lst1) != 9 or sum(check_lst2) != 9:

            return False

   

    for i in range(3):

        for j in range(3): # 구역체크 (총 9개의 구역)

            check_lst3 = [0]*10

            for k in range(3):

                for l  in range(3):

                    check_lst3[lst[i*3+k][j*3+l]] = 1

            if sum(check_lst3) != 9:

                return False

    return True

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

if check(sudo) == True:

    print("YES")

else:

    print("NO")