https://www.acmicpc.net/problem/2580
# solution.
# 빈 칸에 넣을 숫자를 판별하기 위해서는 해당 칸이 속한 행, 열, 3x3 크기의 정사각형 이 3개에 존재하는 숫자를 살펴야 한다.
# 이 3개를 row, col, sqaure 배열로 설정하여, 각 숫자를 포함하고 있는지를 Boolean형으로 나타내게 한다.
# 가령 row[i][j] = True 는 i번째 행은 j라는 숫자를 포함하고 있다는 뜻이다.
# 작은 정사각형은 총 9개가 있으며, make_square 함수는 (x,y)를 받고 해당 칸이 속한 작은 정사각형의 번호를 반환한다.
# recur 함수는 z==81이 되어 마지막 칸까지 탐색을 마치는 경우 답을 출력한다.
# 작은 정사각형은 총 9개가 있으며, make_square 함수는 (x,y)를 받고 해당 칸이 속한 작은 정사각형의 번호를 반환한다.
def make_square(x,y):
return (x//3)*3 + y//3
def recur(z):
# recur 함수는 z==81이 되어 마지막 칸까지 탐색을 마치는 경우 답을 출력하고 True를 리턴한다.
if z==81:
for r in a:
print(' '.join(map(str,r)))
return True
x,y=z//n,z%n
# 0이 아닌 경우 다음 칸을 탐색한다.
if a[x][y]!=0:
return recur(z+1)
# 해당 칸에서 1~9의 숫자 중 행, 열, 작은 정사각형 모두에 없는 수를 넣어본다.
for i in range(1,10):
if not row[x][i] and not col[y][i] and not square[make_square(x,y)][i]:
row[x][i] = col[y][i] = square[make_square(x,y)][i]=True
a[x][y]=i
# 경우의 수들 중 마지막 칸까지 탐색을 성공한 경우 True가 반환되므로, 아래의 제거 과정을 다시 밟지 않고 recur 함수가 종료되도록 True를 반환한다.
if recur(z+1): return True
# 다른 경우의 수를 위해 해당 칸에서 수를 다시 제거한다.
row[x][i] = col[y][i] = square[make_square(x,y)][i]=False
a[x][y]=0
# 마지막 칸까지 탐색을 마치지도, 이번 칸이 0인 경우도 아닌 경우, 실패한 탐색이다.
return False
n=9
a=[list(map(int,input().split())) for _ in range(n)]
# 빈 칸에 넣을 숫자를 판별하기 위해서는 해당 칸이 속한 행, 열, 3x3 크기의 정사각형 이 3개에 존재하는 숫자를 살펴야 한다.
# 이 3개를 row, col, sqaure 배열로 설정하여, 각 숫자를 포함하고 있는지를 Boolean형으로 나타내게 한다.
# 가령 row[i][j] = True 는 i번째 행은 j라는 숫자를 포함하고 있다는 뜻이다.
col=[[False]*10 for _ in range(n)]
row=[[False]*10 for _ in range(n)]
square=[[False]*10 for _ in range(n)]
for i in range(n):
for j in range(n):
if a[i][j]!=0:
row[i][a[i][j]]=True
col[j][a[i][j]]=True
square[make_square(i,j)][a[i][j]]=True
recur(0)
'코딩 테스트 > 백준 강의 연습편' 카테고리의 다른 글
브루트포스) 15658.연산자 끼워넣기(2) (0) | 2022.06.07 |
---|---|
브루트포스) 14888.연산자 끼워넣기 (0) | 2022.06.07 |
브루트포스) 14225.부분수열의 합 (0) | 2022.06.07 |
브루트포스) 1182.부분수열의 합 (0) | 2022.06.07 |
브루트포스) 6603. 로또 (0) | 2022.06.07 |