탐색&시뮬레이션 문제 #10. 스도쿠 검사

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

내 풀이

 

1. 행, 열, 3*3박스 별로 숫자 중복 검사를 위해서 checkRow, checkColumn, checkBox 배열을 만들고 0으로 초기화한다.

 

2. 위 배열의 인덱스를 스도쿠 숫자로 사용하고, 해당 인덱스의 숫자가 발견되었다면 그 배열의 값을 1로 변경한다.

 

3. 위 배열의 값이 1이라면, 이미 숫자가 발견되었다는 의미로 숫자가 중복된다는 것이다. 따라서 이는 스도쿠가 아니기 때문에 else문을 통해 2중 for문을 빠져나간다.

 

4. 이 때, 2중 for문이므로 break 한 번으로는 2중 for문을 빠져나갈 수 없으므로, forBreak 변수를 boolean으로 두어, True 및 False 값을 통해 2중 for문을 빠져나갈 수 있도록 한다.

 

5. 여기서 3*3 박스에서 중복이 있는 지 없는 지 확인하기 위해서, row와 col 배열을 두어 3*3 박스의 중심을 나타냈고, dx와 dy 배열을 두어 중심의 주변부를 확인할 수 있도록 했다.

 

6. break에 걸리지 않고 for문을 완벽히 수행했다면, 중복되는 값이 없는 스도쿠를 의미하기 때문에 "YES"를 출력한다.

 

import sys
#sys.stdin=open("input.txt","rt")
row=[1,1,1,4,4,4,7,7,7] 
col=[1,4,7,1,4,7,1,4,7]
dx=[-1,-1,-1,0,0,0,1,1,1]
dy=[-1,0,1,-1,0,1,-1,0,1]
arr=[list(map(int, input().split())) for _ in range(9)]

checkRow=[0]*10
checkColumn=[0]*10
checkBox=[0]*10
forBreak = False

for i in range(9):
    for j in range(9):
        if checkRow[arr[i][j]]==0:
            checkRow[arr[i][j]]=1
        else:
            print("NO")
            forBreak = True
            break
        if checkColumn[arr[j][i]]==0:
            checkColumn[arr[j][i]]=1
        else:
            print("NO")
            forBreak = True
            break
        if checkBox[arr[row[i]+dx[j]][col[i]+dy[j]]]==0:
            checkBox[arr[row[i]+dx[j]][col[i]+dy[j]]]=1
        else:
            print("NO")
            forBreak = True
            break
    if forBreak:
        break
    checkRow=[0]*10
    checkColumn=[0]*10
    checkBox=[0]*10
else:
    print("YES")

 

 

 

강사님 풀이

 

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

def check(a):
    for i in range(9):
        ch1=[0]*10 # 행 체크
        ch2=[0]*10 # 열 체크
        for j in range(9):
            ch1[a[i][j]]=1
            ch2[a[j][i]]=1
        if sum(ch1)!=9 or sum(ch2)!=9:
            return False
    # 9개의 3*3 그룹 탐색
    for i in range(3):
        for j in range(3):
            ch3=[0]*10
            # 그룹 안의 9개 숫자 탐색
            for k in range(3):
                for s in range(3):
                    ch3[a[i*3+k][j*3+s]]=1
            if sum(ch3)!=9:
                return False
    return True
    
a=[list(map(int,input().split())) for _ in range(9)]

if check(a):
    print("YES")
else:
    print("NO")

 

 

 

배운 점

 

1. 다중 for문을 빠져나가고 싶은 경우, 함수로 만들어서 return 을 통해 빠져나가도록 한다.