1. 문제
  2. 접근
  3. 풀이

문제

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

접근

  • Post not found: boj-9663 BOJ 9663 N-Queen문제와 비슷하게, 백트래킹을 이용한다. 초기에 0이었던 위치에 1~9를 대입해보며 같은 행/열/사각형에 겹치는 숫자가 있는지 promising을 거치며 DFS를 실행한다.

  • 현재 검사하고 있는 칸을 x,y좌표로 두는 것 보다, (0,0)에서부터 순서를 정해 cnt로 정의하면 cnt // 9, cnt % 9로 좌표를 구할 수 있어 편하다.

  • 처음에 cnt==81 조건 이후 return을 넣었더니 출력초과가 떴다. 만족하는 모든 스도쿠의 해를 출력하고 있었던 것이다. 이 때 이용할 수 있는 함수가 exit()으로, 도달하면 컴파일된 프로그램 전체를 종료하기 때문에 처음으로 구한 해만 출력하고 종료할 수 있게 된다.

풀이

BOJ 2239 스도쿠
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
s = [[int(i) for i in input()] for _ in range(9)]
r, c, sq = [[False]*10 for _ in range(9)],[[False]*10 for _ in range(9)],[[False]*10 for _ in range(9)]
for i in range(9):
  for j in range(9):
    x = s[i][j]
    r[i][x] = c[j][x] = sq[(i//3)*3+j//3][x] = True

def solve(cnt):
  global r, c, sq
  if cnt == 81:
    for i in s:
      print(*i, sep='')
    exit()
  x,y = cnt // 9, cnt%9
  if s[x][y] == 0:
    for i in range(1,10):
      if not r[x][i] and not c[y][i] and not sq[(x//3)*3+y//3][i]:
        s[x][y] = i
        r[x][i] = c[y][i] = sq[(x//3)*3+y//3][i] = True
        solve(cnt+1)
        s[x][y] = 0
        r[x][i] = c[y][i] = sq[(x//3)*3+y//3][i] = False
  else:
    solve(cnt+1)

solve(0)