반응형
https://www.acmicpc.net/problem/2580(문제 동일)
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
https://www.acmicpc.net/problem/2239
2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
table = [] for _ in range(9): table.append([x for x in input()]) def search(i, j): nums = [False] * 9 for k in range(9): n = int(table[i][k]) if n != 0: nums[n-1] = True n = int(table[k][j]) if n != 0: nums[n-1] = True gi = (i//3)*3 gj = (j//3)*3 for l in range(gi, gi+3): for m in range(gj, gj+3): n = int(table[l][m]) if n != 0: nums[n-1] = True possible = [] for k in range(9): if nums[k] == False: possible.append(k+1) return possible idx_lst = [] for i in range(9): for j in range(9): if table[i][j] == '0': idx_lst.append([i, j]) def dfs(i): x, y = idx_lst[i] possible = search(x, y) if not possible: return if i == len(idx_lst)-1: # finish table[x][y] = possible[0] for k in range(9): print("".join(map(str,table[k]))) quit() for elem in possible: table[x][y] = elem dfs(i+1) table[x][y] = '0' dfs(0)백트래킹을 어떻게 진행해야 될지 감이 안와서 한참 걸렸던 문제다.
생각해낸 방법은 우선 완전탐색으로 비어있는 곳의 위치를 idx_lst라는 곳에 저장한다.
그리고 dfs를 시작한다.
dfs함수 내에서는 가장먼저 search함수로 빈칸에 들어갈 수 있는 수들을 찾는다. 이 수들이 possible에 저장되어 있다.
그리고 그 안의 원소들로 반복문을 돌리면서 그 안에 다시 dfs를 넣으면 재귀 구조가 완성된다.
주의할 점은 dfs를 끝난 시점에 table[x][y] = '0'과 같이 입력을 초기화해주어야 한다. 나중에 다시 그 위치로 갔을 때 비어있지 않고 다른 값이 들어가있으면 제대로 search가 되지 않는다.
댓글