1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
graph = [list(map(int,input().split())) for _ in range(9)]
go = set([0,1,2,3,4,5,6,7,8,9])
def rowrow():
for i in range(9):
zero_count = 0
zero_index = 0
go = set([0,1,2,3,4,5,6,7,8,9])
for j in range(9):
if graph[i][j]==0:
zero_count+=1
zero_index = j
if zero_count == 1:
go -= set(graph[i])
gogo = list(go)
print(gogo[0])
graph[i][zero_index]=gogo[0]
def colcol() :
for i in range(9):
zero_count = 0
zero_index = 0
go = set([0,1,2,3,4,5,6,7,8,9])
data = set()
for j in range(9):
if graph[j][i]==0:
zero_count+=1
zero_index = j
data.add(graph[j][i])
if zero_count == 1:
go -= set(data)
gogo = list(go)
print(gogo[0])
graph[zero_index][i]=gogo[0]
def dfs(x,y) :
if x>6 or y>6 :
return
zero_count = 0
zero_i = 0
zero_j = 0
go = set([0,1,2,3,4,5,6,7,8,9])
data = set()
for i in range(x,x+3):
for j in range(y,y+3):
if graph[i][j]==0:
zero_count+=1
zero_j = j
zero_i = i
data.add(graph[i][j])
if zero_count == 1:
go -= set(data)
gogo = list(go)
print(gogo[0])
graph[zero_i][zero_j]=gogo[0]
dfs(x+3,y)
dfs(x,y+3)
while True :
count = 0
for i in range(9):
for j in range(9):
if graph[i][j] == 0 :
count +=1
if count == 0 :
break
else :
rowrow()
colcol()
dfs(0,0)
for i in range(9):
print(*graph[i])
|
cs |
나는 이 문제를 풀지 못했다.
왜 못풀었나?
일단 생각을 세가지의 function으로 나누었다.
1. row를 비교해서 0이 1개일때 1~9중에 없는 숫자를 대입
2. col를 비교해서 0이 1개일때 1~9중에 없는 숫자를 대입
3. 3x3 박스를 비교해서 0이 1개일때 1~9 중에 없는 숫자를 대입.
내가 간과했던 것은 스도쿠를 풀때 모두 저런식으로 딱딱 숫자를 알 수 있게 나오지 않는데. 어떤 것은 숫자를 찍어야할때도 있다. 어릴때 스도쿠 풀던 기억을 살려보면, 빈칸이 2개있는데 4, 5를 넣을 수 있는 데 더 이상 정보가 없는 경우 찍어야하는 경우이다.
또한 나는 백트레킹적인 생각도 하지 못했다.
다른분의 풀이
https://hongcoding.tistory.com/118
[백준] 2580 스도쿠 (Python 파이썬)
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로,
hongcoding.tistory.com
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
import sys
graph = []
blank = []
for i in range(9):
graph.append(list(map(int, sys.stdin.readline().rstrip().split())))
for i in range(9):
for j in range(9):
if graph[i][j] == 0:
blank.append((i, j))
def checkRow(x, a):
for i in range(9):
if a == graph[x][i]:
return False
return True
def checkCol(y, a):
for i in range(9):
if a == graph[i][y]:
return False
return True
def checkRect(x, y, a):
nx = x // 3 * 3
ny = y // 3 * 3
for i in range(3):
for j in range(3):
if a == graph[nx+i][ny+j]:
return False
return True
def dfs(idx):
if idx == len(blank):
for i in range(9):
print(*graph[i])
return
for i in range(1, 10):
x = blank[idx][0]
y = blank[idx][1]
if checkRow(x, i) and checkCol(y, i) and checkRect(x, y, i):
graph[x][y] = i
dfs(idx+1)
graph[x][y] = 0
dfs(0)
|
cs |
배운점
dfs의 제한을 0의 갯수를 처음에 다 세고 0의 갯수와 dfs의 depth가 같아지면 종료하게끔 만드셨다.
def checkRect(x, y, a):
nx = x // 3 * 3
ny = y // 3 * 3
for i in range(3):
for j in range(3):
if a == graph[nx+i][ny+j]:
return False
return True
또한 3x3 조건을 탐색할때, nx = x//3 * 3이 눈에 띄었다.
5,2 의 위치를 검사할때 5//3*3 = 3
2//3*3 = 0 이 되므로 해당 박스를 찾을 수 있게 된다.
1 2 3
4 5 6
7 8 9
4번째 위치이다.
그리고 마지막으로
if idx == len(blank):
for i in range(9):
print(*graph[i])
return
이 부분인데
이는 splat operator 이고, 별표 즉, 'Asterisk' 라고도 부를 수 있다.
이를 사용하는 이유는 리스트의 unpacking인데,
print(graph[i]) 였다면 이렇게 출력 되었을 것이 splat operator를 사용해서 ,
이렇게 출력되게 할 수 있었다.
'알고리즘 공부 > 미분류' 카테고리의 다른 글
[백준/JS] 2504 괄호의값 (0) | 2022.02.16 |
---|---|
백준 14888번 파이썬 (0) | 2022.02.09 |
백준 꽃길 14620번 파이썬 (0) | 2022.02.09 |
백준 선수과목 파이썬 (0) | 2022.01.28 |
bfs dfs (0) | 2022.01.14 |