[파이썬 알고리즘 문제풀이 입문] 탐색&시뮬레이션 - 스도쿠 검사

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9x9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3x3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 완성된 9x9 크기의 스도쿠가 주어지면 정확하게 풀었으면 "YES", 잘 못 풀었으면 "NO"를 출력하는 프로그램을 작성하세요.

 

 

 

풀이

• 답변 : Python

import sys
input = sys.stdin.readline

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

    # 그룹 체크
    # 9개의 그룹
    for i in range(3):
        for j in range(3):
            ch3 = [0] * 10
            # 그 안의 9개의 숫자
            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

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

- 행 / 열 / 3x3 그룹 별로 접근해야 한다는 것은 바로 파악할 수 있었지만, 불필요한 for문이나 리스트 변수가 많아져서 방법이 잘못되었다는 것을 파악하고 답안을 확인했다.

- 행 / 열 / 3x3 그룹 별로 확인에 필요한 리스트(ch1, ch2, ch3)가 필요하다. (0으로 초기화)

- 입력받은 리스트를 한 줄 씩 & 각 요소 별로 돌면서(2중 for문), 각 요소의 값을 인덱스로 갖는 리스트(ch1, ch2, ch3)의 값을 1로 변경해준다. (스도쿠는 1~9까지 있기 때문에 0번 인덱스는 사용하지 않는다. == 0번 인덱스의 값은 항상 0)

- ch3 같은 경우에는 조금 다르다. 그룹 별로 확인을 해주어야 하기 때문에, 4중 for문이 필요하고(9개의 그룹을 확인하는 2중 for문 / 그룹 안의 9개의 요소들을 확인하는 2중 for문 / 0~2까지 반복), 그룹의 시작 인덱스가 0, 3, 6 이기 때문에 3을 곱해주어야 한다.

- 스도쿠를 정확하게 풀었다 == 리스트(ch1, ch2, ch3)의 값이 인덱스 0번을 제외하고 모두 1을 갖는다 = 리스트 전체 합이 9이다

- 이에 따라 True/False를 반환하여, 해당 Boolean 값으로 "YES" 또는 "NO"를 출력한다.