[SWEA] D2 - 1974. 스도쿠 검증 in 파이썬

문제 출처

SW Expert Academy

 

문제

스도쿠는 숫자 퍼즐로,가로 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부터 시작한다.)

 

 

---

 

문제 풀이

스도쿠는 가로, 세로, 사각형 범위 각각이 1에서부터 9까지 겹치는 숫자가 없는 퍼즐이다.

 

즉, 세 가지 경우를 모두 나눠 검증해야 한다.

1. 가로줄 검증
2. 세로줄 검증
3. 3*3 사각형 검증

세 가지 검증을 모두 통과할 경우 1을 출력하고 셋 중 하나라도 통과하지 못할 경우 0을 출력하면 된다.

 

 

 

 

 

유효한 스도쿠 검증 방법

리스트를 이용해서 중복되는 숫자를 확인

• 검증을 위한 10 크기의 배열을 만들고, 인덱스 번호를 검증할 숫자 값으로 상정한다.
  (1번째 인덱스는 숫자 1의 중복 판별, 2번째 인덱스는 숫자 2의 중복 판별...)
• 가로, 세로, 사각형 각각의 경우를 함수로 나누어서 검증을 진행한다.
• 가로와 세로는 한 줄씩 탐색하면서 값이 처음 나왔을 경우 검증 배열에 방문 표시를 하고
• 이미 방문한 값일 경우, 유효하지 않은 퍼즐이므로 0을 출력하도록 한다
• 사각형 또한 3*3 크기씩 탐색하고 검증한다.
  (사각형의 시작 인덱스를 다른 사각형과 구분하는 지표로 삼고, 행열을 3 길이만큼 탐색하면 된다)

 

 

---

 

작성 코드

import sys
sys.stdin = open("input.txt", "r")

def row_valid(sudoku):
    for r in range(9):
        visit = [False] * 10  # 1~9 숫자별 방문여부 확인. 0번째 인덱스는 버리는 값
        for c in range(9):
            val = sudoku[r][c]            
            if visit[val] == True:
                return 0
            else:
                visit[val] = True
    return 1

def col_valid(sudoku):
    for c in range(9):
        visit = [False] * 10  # 1~9 숫자별 방문여부 확인. 0번째 인덱스는 버리는 값
        for r in range(9):
            val = sudoku[r][c]
            if visit[val] == True:
                return 0
            else:
                visit[val] = True
    return 1

def square_valid(sudoku):
    for r_start in range(0, 9, 3):
        for c_start in range(0, 9, 3):
            visit = [False] * 10  # 1~9 숫자별 방문여부 확인. 0번째 인덱스는 버리는 값
            for i in range(3):
                for j in range(3):
                    val = sudoku[r_start + i][c_start + j]
                    if visit[val] == True:
                        return 0
                    else:
                        visit[val] = True
    return 1
            
T = int(input())
for test_case in range(1, T + 1):
    sudoku = [list(map(int, input().split())) for _ in range(9)]    # 9*9 크기의 스도쿠
    
    r = row_valid(sudoku)
    c = col_valid(sudoku)
    s = square_valid(sudoku)   

    if (r == 0 or c == 0 or s == 0):
        ans = 0
    else:
        ans = 1
    
    print(f'#{test_case} {ans}')