[SWEA] 스도쿠 검증(1974) - PYTHON

스도쿠의 좌표(9*9 2차원 배열)가 주어지면, 스도쿠가 유효한지(1~9까지의 숫자가 유일하게 등장하는지) 검사하는 문제다.

시간복잡도: O(N)

SW Expert Academy

---

풀이 방법

스도쿠의 9 * 9 좌표에서 세로줄, 가로줄, 3 * 3 사각형에 대해서 숫자를 검사해야 한다.
이를 위해 우선 2차원 배열을 입력받은 다음에 세로줄, 가로줄, 3 * 3 사각형을 각각 차례로 담은 2차원 배열 3개를 만든다.

ex)

입력: 7 3 6 4 2 9 5 8 1 5 8 9 1 6 7 3 2 4 2 1 4 5 8 3 6 9 7 8 4 7 9 3 6 1 5 2 1 5 3 8 4 2 9 7 6 9 6 2 7 5 1 8 4 3 4 2 1 3 9 8 7 6 5 3 9 5 6 7 4 2 1 8 6 7 8 2 1 5 4 3 9

가로배열: [7, 3, 6, 4, 2, 9, 5, 8, 1], [5, 8, 9, 1, 6, 7, 3, 2, 4], [2, 1, 4, 5, 8, 3, 6, 9, 7], [8, 4, 7, 9, 3, 6, 1, 5, 2], [1, 5, 3, 8, 4, 2, 9, 7, 6], [9, 6, 2, 7, 5, 1, 8, 4, 3], [4, 2, 1, 3, 9, 8, 7, 6, 5], [3, 9, 5, 6, 7, 4, 2, 1, 8], [6, 7, 8, 2, 1, 5, 4, 3, 9]

세로배열: [7, 5, 2, 8, 1, 9, 4, 3, 6], [3, 8, 1, 4, 5, 6, 2, 9, 7], [6, 9, 4, 7, 3, 2, 1, 5, 8], [4, 1, 5, 9, 8, 7, 3, 6, 2], [2, 6, 8, 3, 4, 5, 9, 7 ,1], [9, 7, 3, 6, 2, 1, 8, 4, 5], [5, 3, 6, 1, 9, 8, 7, 2, 4], [8, 2, 9, 5, 7, 4, 6, 1, 3], [1, 4, 7, 2, 6, 3, 5, 8, 9]

3 * 3 사각형 배열: [7, 3, 6, 5, 8, 9, 2, 1, 4], [8, 4, 7, 1, 5, 3, 9, 6, 2], [4, 2, 1, 3, 9, 5, 6, 7, 8], [4, 2, 9, 1, 6, 7, 5, 8, 3], [9, 3, 6, 8, 4, 2, 7, 5, 1], [3, 9, 8, 6, 7, 4, 2, 1, 5], [5, 8, 1, 3, 2, 4, 6, 9, 7], [1, 5, 2, 9, 7, 6, 8, 4, 3], [7, 6, 5, 2, 1, 8, 4, 3, 9]

이때 3 * 3 사각형은 편의상 세로 방향을 먼저 배치한다.

빨간색숫자: 3*3 사각형배열의 순서

이렇게 하면 (가로, 세로, 3*3 사각형배열) 각각 2차원 배열에 대해 모든 요소(배열)의 값은 1~9로 이루어져있어야 한다.

이는 배열을 집합으로 만들어서 길이를 구해 길이가 9인지 검사하며 구한다.(입력은 1~9의 숫자이므로, 스도쿠가 성립하려면 각 1차원 배열을 집합으로 만들었을 때 길이가 9여야 한다.)

이때 3 * 3사각형 배열을 구하는 방법은 아래와 같다.

sqrArr = [[arr[i % 3 * 3 + j // 3][i // 3 * 3 + j % 3] for j in range(9)] for i in range(9)]

(i, j 쌍)

→방향의 index는 i // 3 * 3 + j % 3 으로 구할 수 있다.
↓방향의 index는 i % 3 * 3 + j // 3 으로 구할 수 있다.

---

코드

N = int(input())
for k in range(1, N + 1):
    arr = [list(map(int, input().split())) for _ in range(9)]
    rowArr = arr
    colArr = [[arr[i][j] for i in range(9)] for j in range(9)]
    sqrArr = [[arr[i % 3 * 3 + j // 3][i // 3 * 3 + j % 3] for j in range(9)] for i in range(9)]
    answer = 1
    for row, col, sqr in zip(rowArr, colArr, sqrArr):
        if len(set(row)) == len(set(col)) == len(set(sqr)) == 9:
            continue
        else:
            answer = 0
            break
    print("#", k, " ", answer, sep="")

주석 추가

N = int(input()) # TC 갯수
for k in range(1, N + 1):
    arr = [list(map(int, input().split())) for _ in range(9)] # 2차원 배열 입력
    rowArr = arr #가로 배열은 입력받은 배열과 동일
    colArr = [[arr[i][j] for i in range(9)] for j in range(9)] #새로 배열 변환
    sqrArr = [[arr[i % 3 * 3 + j // 3][i // 3 * 3 + j % 3] for j in range(9)] for i in range(9)] # 3 * 3 사각형 각각을 1차원 배열로 변환
    answer = 1 #출력할 정답
    for row, col, sqr in zip(rowArr, colArr, sqrArr): # 2차원배열에서 각각 1차원 배열을 꺼내서
        if len(set(row)) == len(set(col)) == len(set(sqr)) == 9: # 집합으로 변환했을때 길이가 모두 9이면 
            continue # 통과
        else: #아니면 (스도쿠 조건 충족 X)
            answer = 0 #정답 0으로 설정
            break # 반복 중단
    print("#", k, " ", answer, sep="") #정답 출력