난이도
Gold 4
풀이 참고 유무
?
막힌 부분
행과 열과 3x3의 사각형에서 스도쿠가 되는지 확인하는 방법 중 시간복잡도를 최대한 줄이는데에서 막혔다.
문제
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
예제 입력
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
예제 출력
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1
문제 검토
n은 9로 고정이기 때문에 구현하는데 더 집중해야되는 문제이다.
풀이(python)
Python
from sys import stdin
input=stdin.readline
sudoku=[list(map(int,input().split())) for _ in range(9)]
zero=[]
for x in range(9):
for y in range(9):
if sudoku[x][y]==0:
zero.append([x,y])
end_depth=len(zero)
def check(x,y,target):
#가로 확인
for i in range(9):
if sudoku[x][i]==target:
return False
#세로 확인
for i in range(9):
if sudoku[i][y]==target:
return False
#3x3 사각형 확인
nx=x//3*3
ny=y//3*3
for i in range(3):
for j in range(3):
if sudoku[nx+i][ny+j] == target:
return False
return True
def dfs(depth,idx):
if depth==end_depth:
for y in range(9):
print(*sudoku[y])
exit()
r=zero[idx][0]
c=zero[idx][1]
for x in range(1,10):
if check(r,c,x):
sudoku[r][c]=x
dfs(depth+1,idx+1)
sudoku[r][c]=0
dfs(0,0) 아이디어
#먼저 0인 좌표들을 전부 다 찾는다.abs
#0인 좌표들마다 1~9까지 대입해보며 넣을 수 있는지 확인한다.abs
#만약 안될 떄는 결국 원인인 부분까지 올라가서 다른 수를 대입하며 반복하게 될 것이다.
#세로 확인 -> 그 열에 넣으려고 하는 수가 있는지 찾는다
#가로 확인 -> 그 행에 넣으려고 하는 수가 있는지 찾는다
#3x3칸 확인 -> 해당 좌표 x,y를 각각 3으로 나누고 3을 곱하면 3의 배수로 해당하는 좌표에 시작점이 될 것이다.abs
#-> for문으로 nx+x ,ny+y로 돌며 넣으려고 하는 수가 있는지 확인한다.
#모든 빈칸은 채우면 출력
걸린 시간
1:04:54
총평
확인하는 부분을 구현하는 과정과 가로열 기준으로 전에 풀었던 문제처럼 백트랙킹을 돌리려다가 시간을 많이 허비했다.
결국 이 문제도 빈 곳부터 채워보며 되는 과정 안되는 과정을 모두 탐색해봐야한다.
