[초기 접근 방법]
스도쿠의 조건
: 행, 열, 네모칸 모두 1가지 숫자만 있는 것
기본적으로 완전탐색
- 백트래킹으로 넣었다 뺐다 하면 단축되지 않을까?
- k 값은 스도쿠 값으로, range(1, 10)으로 설정해줘야 함
- 백트래킹의 종료 조건
→ 스도쿠의 마지막 빈 칸이 채워졌을 때 종료한다.
[생각]
1) 인덱스 3*3 구역의 스도쿠 구역 체크할 때 인덱스 설정이 틀려서 20분을 썼다..
2) 그리고 한 가지 유의할 점이
스도쿠의 빈 칸의 값이 1~9 모두 유효하지 않을 때는,
이전 값이 틀린 것이므로 빠르게 return을 하여 해당 스도쿠의 빈 칸 dfs()를 끝내준다.
3) 아니면 스도쿠 빈 칸에 대한 1~9 check()를 반복문 안에서 하는 것이 아니라
dfs() 함수 첫번째에서 check()를 해주는 방법 또한 있다.
4) 추가로 시간복잡도 측면에서 효율적인 풀이는
스도쿠 빈 칸 좌표들을 튜플로 저장한 후, 해당 좌표들에 대해서만 dfs()를 하는 방법도 있을 수 있다.
[코드]
# 풀이 시간 : 1시간
# 시간복잡도 : O(9*9*9 - X)
# 공간복잡도 : O(9*9)
# 참고 : -
lst = [list(map(int, input())) for _ in range(9)]
cnt = 0
def check(row, col, num):
for i in range(0, 9):
if lst[row][i] == num:
return False
for i in range(9):
if lst[i][col] == num:
return False
quotR = row // 3
quotC = col // 3
for i in range(3):
for j in range(3):
if lst[3*quotR+i][3*quotC+j] == num:
return False
return True
def dfs(R, C):
global cnt
global finalX, finalY
if finalX == R and finalY == C:
for i in range(9):
for j in range(9):
print(lst[i][j], end="")
print()
exit()
for i in range(9):
for j in range(9):
# 빈 칸 넣기
if lst[i][j] == 0:
for k in range(1, 10):
if check(i, j, k):
lst[i][j] = k
dfs(i, j)
lst[i][j] = 0
# 1~9 까지 모두 안 되었을 경우, 이전 lst[i][j] 값을 다른 값을 넣어줘야 함
# cf. check[9] == True 일 때, final까지 계속 dfs 탐색함.
if k == 9:
return
finalX = 0
finalY = 0
for i in range(9):
for j in range(9):
if lst[i][j] == 0:
finalX = i
finalY = j
dfs(0, 0)
'Algorithm > Brute Fource' 카테고리의 다른 글
[백준] 1079번 마피아 _ Python (0) | 2024.01.29 |
---|---|
[백준] 18111번 마인크래프트 _ Python (0) | 2024.01.16 |
[백준] 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 _ Python (1) | 2023.11.16 |
[백준] 15721번 번데기 _ Python (1) | 2023.11.14 |
[백준] 1548번 부분 삼각 수열 _ Python (0) | 2023.11.10 |