[SWEA] 1974. 스도쿠 검증

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq

SW Expert Academy

나의 방식

• 각 행, 각 열에서 중복된 숫자가 나오면 안 됨 
• 3 x 3 행렬 내로 중복된 숫자가 나오면 안 됨 
  • (0, 0) 을 기준으로 0, 1, 2 좌표 값을 갱신하며 수 검사 
  • 그 후, 3 칸씩 이동해 다시 검사 

count = [0, 0, ... , 0] 배열을 업데이트 하는 방식을 통해 중복 여부를 검사했다. 

def check(arr):
    count = [0] * 10

    # 행 검사 
    for i in range(9):
        for j in range(9):
            if(count[arr[i][j]] == 1):
                return 0
            else:
                count[arr[i][j]] = 1
        count = [0] * 10
    
    # 열 검사 
    for i in range(9):
        for j in range(9):
            if(count[arr[j][i]] == 1):
                return 0
            else:
                count[arr[j][i]] = 1
        count = [0] * 10
    
    # 3x3 검사
    for i in range(3):
        for j in range(3):
            for k in range(3):
                for l in range(3):
                    if(count[arr[i*3+k][j*3+l]] == 1):
                        return 0
                    else:
                        count[arr[i*3+k][j*3+l]] = 1
            count = [0] * 10
    return 1

T = int(input())

for test_case in range(1, T + 1):
    
    arr = []
    for i in range(9):
        arr.append(list(map(int, input().split())))

    print(check(arr))

 

문제는 해결됐으나, 4중 반복문을 사용해 업데이트 한다는 점이 걸렸다.

더 효율적인, 시간 복잡도를 계산할 수 있는 방법은 없는지 더 알아보기로 했다. 

 

다른 방식

claude 에게 더 효율적인 방안이 없는지 물어보았다. 

아래는 claude가 제시한 한 번의 순회로 모든 검사를 하는 방법이다. 

def check(arr):
    # 행, 열, 3x3 박스를 동시에 검사
    for i in range(9):
        row = [0] * 10
        col = [0] * 10
        box = [0] * 10
        
        for j in range(9):
            # 행 검사
            if row[arr[i][j]] == 1:
                return 0
            row[arr[i][j]] = 1
            
            # 열 검사
            if col[arr[j][i]] == 1:
                return 0
            col[arr[j][i]] = 1
            
            # 3x3 박스 검사
            box_row = (i // 3) * 3 + j // 3
            box_col = (i % 3) * 3 + j % 3
            if box[arr[box_row][box_col]] == 1:
                return 0
            box[arr[box_row][box_col]] = 1
    
    return 1

 

3 x 3 박스 검사에서 왜 이렇게 인덱스를 지정하는지 어려웠는데, 

• box_row = (i // 3) * 3 + j // 3
• box_col = (i % 3) * 3 + j % 3

사진처럼 쉽게 생각하면 i 는 9개의 박스를 순차적으로 순회하는 역할이다.

내 코드에서 보면 i, j로 좌표 이동하는 것과 같은 역할이다. 

 

j는 박스 내에서의 위치를 나타내는 것이다. 

내 코드에서 k와 l로 좌표를 이동하는 것과 같은 역할이다. 

 

행은 i // 3 으로 열은 i % 3 으로 나타내는데 이 이유는 사진의 좌표 값만 봐도 알 수 있다. 

• i // 3
  
  • i=0,1,2 → 0 첫째 행
  • i=3,4,5 → 1 둘째 행
  • i=6,7,8 → 2 셋째 행
• i % 3
  • i=0,3,6 → 0 첫째 열
  • i=1,4,7 → 1 둘째 열
  • i=2,5,8 → 2 셋째 열 

 

이 풀이 방식을 본 뒤, 나의 4중 반복문을 아래와 같이 개선했다.

결과적으로 2중 반복문만으로 3 x 3 행렬 검사를 할 수 있게 되었다. 

# 3 x 3 검사 (개선)
    for i in range(9):
        for j in range(9):
            row = (i // 3) * 3 + (j // 3)
            col = (i % 3) * 3 + (j % 3)

            if(count[arr[row][col]] == 1):
                return 0
            else:   
                count[arr[row][col]] = 1
        count = [0] * 10