백준 2580. 스도쿠

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

괴랄해 보여서 쫄리지만 생각보다는, '생각보다는' 쉬운 문제. 그래도 아직 어렵긴 하다.

 

기본적인 dfs에서 N-Queens와 다르게 꼼짝없이 이중 리스트를 사용해야 하는데, 이에 따라 검사하는 방법도 가로, 세로, 스도쿠의 3*3 작은 사각형을 검사해줘야 한다. 개인적으로 사각형 검사 부분이 가장 까다로웠던 것 같다.

 

기본적인 아이디어는 다음과 같다.

1. 기존 dfs와는 조금 다르게, 빈 공간이 아무렇게나 주어지지 않으므로 이에 대한 정보가 필요하다.

2. 빈 공간의 x, y를 가지고 검사 메서드를 짜야 한다.

 

빈 공간은 0으로 주어지기에 배열을 받고 나서 반복문을 통해 빈 공간의 좌표를 모두 담아주고, 이를 통해 dfs를 진행했다.

 

sudoku = []
blanks = []
for i in range(9): #스도쿠 맵 초기화
	sudoku.append(list(map(int, input().split())))

for i in range(9):
	for j in range(9):
		if sudoku[i][j] == 0: #빈칸 인덱스 값 받기
			blanks.append([i, j])
def check_row(x, num): # 세로 검사
	for i in range(9):
		if num == sudoku[x][i]:
			return False
	return True

def check_col(y, num): # 가로 검사
	for i in range(9):
		if num == sudoku[i][y]:
			return False
	return True

def check_rectangle(x, y, num): # 3x3 사각형 검사
	x = x//3 * 3 #제일 왼쪽 위 x값 찾기
	y = y//3 * 3 #제일 왼쪽 위 y값 찾기
	for i in range(3): # 3x3 검사
		for j in range(3):
			if sudoku[x + i][y + j] == num:
				return False
	return True
	
def dfs(blank_idx):
	if len(blanks) == blank_idx:
		for i in range(9):
			for j in range(9):
				print(sudoku[i][j], end= " ")
			print()
		exit()
	x = blanks[blank_idx][0]
	y = blanks[blank_idx][1]
	for i in range(1, 10):
		if check_row(x, i) and check_col(y, i) and check_rectangle(x, y, i):
			sudoku[x][y] = i
			dfs(blank_idx + 1)
			sudoku[x][y] = 0 #탈락이면 원활한 검사를 위해 값 초기화

dfs(0)