.PNG)
20.스도쿠 검사
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9
개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다.
예를 들어 다음을 보자.
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
위 그림은 스도쿠를 정확하게 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오
고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색
깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
완성된 9×9 크기의 수도쿠가 주어지면 정확하게 풀었으면 “YES", 잘 못 풀었으면 ”NO"를 출
력하는 프로그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 완성된 9×9 스도쿠가 주어집니다.
▣ 출력설명
첫째 줄에 “YES" 또는 ”NO"를 출력하세요
<내 풀이>
- 풀지 못했다
for i in range(9) :
rows=[]
columns=[]
for j in range(9) :
rows.append(a[i][j])
columns.append(a[j][i])
if len(rows)==len(set(rows)) and len(columns)==len(set(columns)):풀다가 각행/ 각열까지 체크하는 건 구현했는데
3*3박스들을 어떻게 비교하는지 몰라서 구현에 실패하고 말았다
<풀이>
- 설명
=>이 체크리스트의 ch[1]부터 ch[9]의 합이 9이면 된다
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
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")<다른 분 풀이> : 3*3 그룹의 비교
- 그룹의 경우만 비교를 한 것이다
lst=[list(map(int, input().split())) for _ in range(9)]
new_list=[]
for i in range(0,9,3):
for j in range(0,9,3):
new_list.append(lst[i][j:j+3]+lst[i+1][j:j+3]+lst[i+2][j:j+3])
for i in new_list:
i.sort()
if i != list(range(1,10)):
print("NO")
break
else:
print("YES")<반성점>
-
저번에 배운 것을 잘 복습하고 활용하는 것을 습관화하자,
이건 에라스토네 체에서 체크리스트 활용하면 되는 것 -
별도의 0으로 된 체크리스트 만들ㅇ서 인덱스 번호로 활용하는 것 잊지 말자
<배운 점>
-
체크리스트 활용하기(에라스토네체 소수찾기문제, 중복 여부 체크 문제) :
행/열에 연속된 수가 빠짐없이 들어가 있는지 확인할 때는 체크용 리스트를 초기화하여 행/열의 숫자를 체크용 리스트의 인덱스에 대응시켜서 그 위치에 1을 할당하는 반복문을 작성한다. 그래서 체크용 리스트의 원소의 합이 연속된 수의 개수와 같은지 확인한다. -
다른 분의 풀이에서
for i in range(0,9,3):
for j in range(0,9,3):
new_list.append(lst[i][j:j+3]+lst[i+1][j:j+3]+lst[i+2][j:j+3])
+lst[i+1][j:j+3]+lst[i+2][j:j+3])이 부분이 인상깊었다
특히 append 할때 리스트를 for i in range(0,9,3):
> for j in range(0,9,3):
new_list.append(lst[i]**[j:j+3]**+lst[i+1]**[j:j+3]**+lst[i+2]**[j:j+3]**)
-> 이런식으로 처리한 것을 새로 알게 되었다 (**표시 해놓은데)
나는 저기서 아래와 같이 구현했는데 실패했었다
for i in range(0,9,3) :
sqr=[]
for j in range(s,e+1) :
sqr.append(a[i][j])
sqr.append(a[i+1][j])
sqr.append(a[i+2][j])
print(sqr)
if len(sqr)!=len(set(sqr)) :
print('NO')s,e로는 원래 늘어나는 식으로 하려고 했는데 위의 (0,9,3)이 세번밖에 안돌다보니 구현에 실패했었다
원인은 j값을 변화시킬 방법을 찾지 못했기 때문이다
for i in range(0,9,3) :
sqr=[]
for j in range(s,e+1) :
sqr.append(a[i][j])
sqr.append(a[i+1][j])
sqr.append(a[i+2][j])
print(sqr)이렇게 하면 sqr은
[1, 5, 9, 4, 7, 8, 3, 2, 6]
[3, 4, 7, 9, 6, 2, 1, 8, 5]
[2, 6, 8, 3, 1, 5, 7, 9, 4]
j가 변하는 것이 없기 때문에 이렇게 세개만 출력되어서 나온다, 저분의 풀이도 나중에 활용해볼 수 있도록 하자
- 그룹탐색 다른 방법 (4중 중첩 for)
for i in range(3) :
for j in range(3) :
h3=[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(1) i(0, 1, 2) / j(0, 1, 2) 해서 총 9번 돌면서 9개의 그룹을 체크
(2) k(0, 1, 2)/ j(0, 1, 2) 해서 총 9번 돌면서 한개의 그룹안에 있는 9개의 숫자를 체크 ...
===>이거 진짜 구현하기 어려운 코드라는 생각이 듬
복습 잘해서 나중에 곡 자유자재로 구현할 수 있게 노력하자
