파이썬 알고리즘-20 (탐색)스도쿠

jiffydev·2020년 8월 28일
0

Algorithm

목록 보기
21/134
post-thumbnail

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

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

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

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

내 코드

lst=[list(map(int, input().split())) for _ in range(9)]
new_list=[]
for i in range(0,9,3):
    for j in range(0,9,3):
        new_list.append(lst[i][j:j+3]+lst[i+1][j:j+3]+lst[i+2][j:j+3])

for i in new_list:
    i.sort()
    if i != list(range(1,10)):
        print("NO")
        break
else:
    print("YES")

테스트 해보면 다 맞았다고 나오기는 하는데, 생각해보니 3x3사각형 안에 1~9까지 있는지만 체크해서 틀림.

풀이

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을 할당하는 반복문을 작성한다. 그래서 체크용 리스트의 원소의 합이 연속된 수의 개수와 같은지 확인한다.
profile
잘 & 열심히 살고싶은 개발자

0개의 댓글