[SWEA-1974][Python] 스도쿠 검증

문제

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

 

예제

[입력]	[출력]
10 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 …	#1 1 ...

 

문제 해결 방법

• 스도쿠의 숫자가 들어 있는 2중 리스트에서 아래와 같은 순서대로 1부터 9까지의 숫자가 들어 있는지 확인한다.

1. 가로 방향 (→)
2. 세로 방향 (↓)
3. 3×3 (□)

 

• 중복된 숫자가 들어갈 수 없는 집합(set) 객체를 이용하면 간단하게 1부터 9까지의 숫자가 들어 있는지 확인할 수 있다. 

			
			
			
		
def solution(matrix):
    # 행 검사
    for row in matrix:
        if len(set(row)) != 9:
            return 0
    
    # 열 검사
    for column in range(9):
        column = [matrix[row][column] for row in range(9)]
        
        if len(set(column)) != 9:
            return 0
    
    # 3x3 검사
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            mini_matrix = []
 
            for x in range(0, 3):
                for y in range(0, 3):
                    mini_matrix.append(matrix[i + x][j + y])
            
            if len(set(mini_matrix)) != 9:
                return 0
    
    return 1

 

코드

집합(set)을 이용한 코드

			
			
			
		
def solution(matrix):
    # 행 검사
    for row in matrix:
        if len(set(row)) != 9:
            return 0
    
    # 열 검사
    for column in range(9):
        column = [matrix[row][column] for row in range(9)]
        
        if len(set(column)) != 9:
            return 0
    
    # 3x3 검사
    for i in range(0, 9, 3):
        for j in range(0, 9, 3):
            mini_matrix = []
 
            for x in range(0, 3):
                for y in range(0, 3):
                    mini_matrix.append(matrix[i + x][j + y])
            
            if len(set(mini_matrix)) != 9:
                return 0
    
    return 1
 
T = int(input())
 
for test_case in range(1, 1 + T):
    matrix = []
 
    for i in range(9):       
        row = list(map(int, input().split()))
        matrix.append(row)
    
    answer = solution(matrix)    # 겹치는 숫자가 없을 경우 1, 있을 경우 0
    
    print(f"#{test_case} {answer}")

 

정렬(sort)을 이용한 코드

• 행과 열, 3 × 3구간의 요소들을 오름차순으로 정렬시키고 비교 기준 리스트(comp_nums_list)와 비교하는 방식이다. 

			
			
			
		
T = int(input())
 
for test_case in range(1, 1 + T):
    matrix = []
 
    for i in range(9):        
        row = list(map(int, input().split()))
        matrix.append(row)
    
    answer = 1    # 겹치는 숫자가 없을 경우 1, 있을 경우 -1
    comp_nums_list = [item for item in range(1, 10)]    # 비교할 대상
 
    # (1) 가로줄(-) 체크
    for i in range(9):
        row_items = []
 
        for j in range(9):
            row_items.append(matrix[i][j])
 
        row_items.sort()
 
        if row_items != comp_nums_list:
            answer = 0
            break
    
    # (2) 세로줄(|) 체크
    for j in range(9):
        column_items = []
 
        for i in range(9):
            column_items.append(matrix[i][j])
 
        column_items.sort()
 
        if column_items != comp_nums_list:
            answer = 0
            break
    
    # (3) 3 x 3 사각형(ㅁ) 체크
    for i in range(0, 7, 3):
        for j in range(0, 7, 3):
            mini_matrix_nums = []
            
            for k in range(3):
                for l in range(3):
                    mini_matrix_nums.append(matrix[i + k][j + l])
            
            mini_matrix_nums.sort()
 
            if mini_matrix_nums != comp_nums_list:
                answer = 0
                break
    
    print(f"#{test_case} {answer}")

 

 

참고

• 난이도: D2