문제 출처 : [SWEA] 1974 스도쿠 검증

문제

스도쿠는 숫자퍼즐로, 가로 9칸 세로 9칸으로 이루어져 있는 표에 1 부터 9 까지의 숫자를 채워넣는 퍼즐이다.

같은 줄에 1 에서 9 까지의 숫자를 한번씩만 넣고, 3 x 3 크기의 작은 격자 또한, 1 에서 9 까지의 숫자가 겹치지 않아야 한다.

입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다.

제약 사항

1. 퍼즐은 모두 숫자로 채워진 상태로 주어진다.

2. 입력으로 주어지는 퍼즐의 모든 숫자는 1 이상 9 이하의 정수이다.

입력

입력은 첫 줄에 총 테스트 케이스의 개수 T가 온다.

다음 줄부터 각 테스트 케이스가 주어진다.

테스트 케이스는 9 x 9 크기의 퍼즐의 데이터이다.

출력

테스트 케이스 t에 대한 결과는 “#t”을 찍고, 한 칸 띄고, 정답을 출력한다.

(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

코드

import sys
sys.stdin = open('1974_sudoku.txt')


# 스도쿠를 판별하는 함수 (스도쿠 리스트, 스도쿠 크기)
def sudoku(field, N):
    # 스도쿠의 크기인 9만큼 반복
    for i in range(N):
        num_row = [0] * (N + 1)     # 가로줄의 중복을 확인할 리스트 생성, 인덱스 초과 방지 위해 +1
        num_col = [0] * (N + 1)     # 세로줄의 중복을 확인할 리스트 생성
        for j in range(N):
            row = field[i][j]       # 가로 기준 현재 인덱스 위치의 값 저장
            col = field[j][i]       # 세로 기준 현재 인덱스 위치의 값 저장
            if num_row[row]:        # 현재 값이 중복되었을 경우 return 0
                return 0
            if num_col[col]:
                return 0
            num_row[row], num_col[col] = 1, 1   # 중복이 없을 경우 값을 1로 바꿔줌

            # i,j 가 0, 3, 6인 경우
            if i % 3 == 0 and j % 3 == 0:
                num_square = [0] * (N + 1)      # 3X3의 영역에 중복값이 있는지 확인하기 위한 리스트
                # 해당 구간 확인
                for k in range(3):
                    for q in range(3):
                        square = field[k + i][q + j]
                        if num_square[square]:      # 중복 값이 있을 경우 0 return
                            return 0
                        num_square[square] = 1      # 중복 값이 없을 경우 1로 변경
    return 1    # 반복문이 끝날 때 까지 return 되지 않았음, 스도쿠 완성


T = int(input())
for tc in range(1, T + 1):
    N = 9   # 스도쿠의 크기
    field = [list(map(int, input().split())) for _ in range(N)]
    result = sudoku(field, N)    # 함수의 return 값ㅇ르 받아 올 변수

    print(f'#{tc} {result}')

풀이 방법

우선 크게 가로줄과 세로줄 탐색, 3X3 영역 탐색을 나눠서 풀이했다. 가로줄과 세로줄의 경우 한 줄씩 탐색하며 겹치는 숫자가 있는 경우 바로 0을 return 해주었다. 3X3 영역의 경우 처음에는 델타값을 활용하여 모든 방향에 대해 검사를 하려고 했으나 잘 되지 않아서 다른 방법을 찾아봤다. 결국 모듈러 연산을 활용하여 3으로 나누어 떨어지는 경우 이중 for문을 각각 3번씩 반복하면서 값들을 판별하는 방식으로 코드를 작성하였다.