스토쿠 검사
📄 문제
스도쿠는 매우 간단한 숫자 퍼즐이다.
9×9 크기의 보드가 있을 때, 각 행과 각 열,
그리고 9 개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다.
예를 들어 다음을 보자.
위 그림은 스도쿠를 정확하게 푼 경우이다.
각 행에 1부터 9까지의 숫자가 중복 없이 나오고,
각 열에 1부터 9까지의 숫자가 중복 없이 나오고,
각 3×3짜리 사각형(9개이며, 위에서 색 깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES",
잘못 풀었으면 ”NO"를 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 완성된 9×9 스도쿠가 주어집니다.
▣ 출력설명
첫째 줄에 “YES" 또는 ”NO"를 출력하세요.
▣ 입력예제
1 4 3 6 2 8 5 7 9
5 7 2 1 3 9 4 6 8
9 8 6 7 5 4 2 3 1
3 9 1 5 4 2 7 8 6
4 6 8 9 1 7 3 5 2
7 2 5 8 6 3 9 1 4
2 3 7 4 8 1 6 9 5
6 1 9 2 7 5 8 4 3
8 5 4 3 9 6 1 2 7
▣ 출력예제
YES
🧞 풀이 (실패: 45 합을 기준으로 했는데 반례 존재)
# 실패
# 45 합을 기준으로 만든 수도쿠
# 값이 중복되더라도 합이 45가 되는 반례가 존재함
'''
각 사각형의 합
a[0][0] a[0][1] a[0][2]
a[1][0] a[1][1] a[1][2]
a[2][0] a[2][1] a[2][2]
a[0][3] a[0][4] a[0][5]
a[1][3] a[1][4] a[1][5]
a[2][3] a[2][4] a[2][5]
a[0][6] a[0][7] a[0][8]
a[1][6] a[1][7] a[1][8]
a[2][6] a[2][7] a[2][8]
a[3][0] a[3][1] a[3][2]
a[4][0] a[4][1] a[4][2]
a[5][0] a[5][1] a[5][2]
a[3][3] a[3][4] a[3][5]
a[4][3] a[4][4] a[4][5]
a[5][3] a[5][4] a[5][5]
a[3][6] a[3][7] a[3][8]
a[4][6] a[4][7] a[4][8]
a[5][6] a[5][7] a[5][8]
a[6][0] a[6][1] a[6][2]
a[7][0] a[7][1] a[7][2]
a[8][0] a[8][1] a[8][2]
a[6][3] a[6][4] a[6][5]
a[7][3] a[7][4] a[7][5]
a[8][3] a[8][4] a[8][5]
a[6][6] a[6][7] a[6][8]
a[7][6] a[7][7] a[7][8]
a[8][6] a[8][7] a[8][8]
3개 * 3개 만큼 이중반복하면 될 듯!
'''
sudoku = [list(map(int, input().split())) for _ in range(9)]
cnt1 = 0
cnt2 = 0
cnt3 = 0
for i in range(9):
print(sum(sudoku[i]))
if sum(sudoku[i]) == 45:
cnt1 = 0
else:
cnt1 = 1
tmp = 0
for j in range(9):
tmp += sudoku[j][i]
print(tmp)
if tmp == 45:
cnt2 = 0
else:
cnt2 = 1
for l1 in range(3):
for l2 in range(3):
tmp2 = 0
tmp2 += sudoku[l1 * 3][l2 * 3]
tmp2 += sudoku[l1 * 3][l2 * 3 + 1]
tmp2 += sudoku[l1 * 3][l2 * 3 + 2]
tmp2 += sudoku[l1 * 3 + 1][l2 * 3]
tmp2 += sudoku[l1 * 3 + 1][l2 * 3 + 1]
tmp2 += sudoku[l1 * 3 + 1][l2 * 3 + 2]
tmp2 += sudoku[l1 * 3 + 2][l2 * 3]
tmp2 += sudoku[l1 * 3 + 2][l2 * 3 + 1]
tmp2 += sudoku[l1 * 3 + 2][l2 * 3 + 2]
print(tmp2)
if tmp2 == 45:
cnt3 = 0
else:
cnt3 = 1
if cnt1 == 1 or cnt2 == 1 or cnt3 == 1:
print('NO')
else:
print('YES')
다른 사람 풀이
# 행을 체크하는 리스트
# 열을 체크하는 리스트
# 그룹을 체크하는 리스트를 만들어서 확인
'''
ch = [0] * 10
ch1 행
ch2 얄
ch3 그룹
ch[a[i][j]] = 1
sum(ch) != 9
잘못된 스토쿠임
'''
def check(tmp):
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
for i in range(3):
for j in range(3):
ch3 = [0] * 10
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')
'🧩 Algorithm > 🟨 Python' 카테고리의 다른 글
[파이썬 알고리즘] 이분 검색 (0) | 2022.08.01 |
---|---|
[파이썬 알고리즘] 격자판 회문수 (0) | 2022.07.26 |
[파이썬 알고리즘] 봉우리 (0) | 2022.07.26 |
[파이썬 알고리즘] 곳감(모래시계) (0) | 2022.07.26 |
[파이썬 알고리즘] 사과나무(다이아몬드) (0) | 2022.07.26 |