1️⃣서론
백준 문제 2580번 스도쿠 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣문제 설명
이 문제는 N * N 의 스도쿠판의 빈칸에 가능한 답의 후보를 찾는 문제입니다.
보통 스도쿠 문제는 대표적인 백트래킹 문제로 유명하기도 합니다.
혹시 백트래킹을 처음들어본다면 제가 개념을 정리해놓은 곳을 가보시면 될 것 같습니다.
3️⃣풀이
스도쿠의 대략적인 풀이 과정은 다음 그림과 같습니다.
스도쿠라는 게임은 다음과 같은 규칙이 정해져 있습니다.
- 가로의 9칸이 1~9까지 하나씩 들어가 있다.
- 세로의 9칸이 1~9까지 하나씩 들어가 있다.
- 3*3의 정사각형이 1~9까지 하나씩 들어가 있다.
백트래킹으로 다음의 조건을 지키며 하나씩 수를 넣어보며 탐색을 해보는 것이 방법이라고 할 수 있겠습니다.
주의해야할 점은 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다. 입니다.
4️⃣ 소스코드
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
import sys
# 가로 체크
def horizontal(x, val):
if val in arr[x]:
return False
return True
# 세로 체크
def vertical(y, val):
for i in range(9):
if val == arr[i][y]:
return False
return True
# 3x3 체크
def bythree(x, y, val):
nx = x//3 * 3
ny = y//3 * 3
for i in range(3):
for j in range(3):
if val == arr[nx+i][ny+j]:
return False
return True
def dfs(index):
if index == len(zeros):
for i in arr:
for j in i:
print(j, end=" ")
print()
sys.exit(0) #하나의 답만 출력해야하므로 시스템을 종료한다 return으로 하면 오답이됨
# 1부터 9까지 탐색하며 답이 될 수 있으면 넣고 다음 dfs로 이동
for i in range(1,10):
nx = zeros[index][0]
ny = zeros[index][1]
if horizontal(nx,i) and vertical(ny,i) and bythree(nx,ny,i):
arr[nx][ny]=i
dfs(index+1)
arr[nx][ny]=0
arr = []
for i in range(9):
arr.append(list(map(int,input().split())))
zeros = [(i, j) for i in range(9) for j in range(9) if arr[i][j] == 0]
dfs(0)
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
