백준_2239_스도쿠

문제

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

2239번: 스도쿠

풀이

1) dfs

깊이/너비 우선 탐색을 할 때 재귀를 잘 사용하지 않았다. 이 문제를 반복문으로 풀었더니, pypy3로 제출하더라도 시간초과가 발생했다. (물론 이 방법으로 푸는 다른 방법도 있겠지만... ) 

백트래킹이 필요한 경우에 기존에는 stack에 배열 자체를 넣어서 반복문을 돌렸는데,

이런 경우 재귀를 사용할 수 있음을 알아두자.

2) 논리

unknown에 0으로 표시된 위치 정보를 저장한다.

unknown에 들어갈 수 있는 candidate를 구한다.

• [1, 2, 3, 4, 5, 6, 7, 8, 9]에서
• 가로방향에 있는 숫자를 제거한다.
• 세로방향에 있는 숫자를 제거한다.
• 3*3 블록에 있는 숫자를 제거한다.

unknown에 들어갈 수 있는 값을 넣어보면서, 스도쿠가 완성되면 탐색을 멈춘다.

3) 제출

python으로 제출해서 시간초과를 통과하지 못했다. (pypy3로 제출했다)

코드

import sys
input = sys.stdin.readline

N = 9
board = [list(map(int, input().strip().split())) for i in range(N)]

rowCandidate = [set(range(1, N+1)) for i in range(N)]
colCandidate = [set(range(1, N+1)) for i in range(N)]
blockCandidate = [[set(range(1, N+1)) for j in range(N)] for i in range(N)]
flag = False # answer 한번만 출력

unknown = list()
for i in range(N) : 
    for j in range(N) : 
       # 각 행/열/블록마다 이미 들어있는 수를 제거
        rowCandidate[i] -= {board[i][j]}
        colCandidate[j] -= {board[i][j]}
        blockCandidate[i//3][j//3] -= {board[i][j]}
        
        # 비어있는 칸을 저장
        if board[i][j] == 0 : 
            unknown.append((i, j))

def pprint() : 
    for i in range(N) : 
        for j in range(N) : 
            print(board[i][j], end = " ")
        print()    

def find(idx) : 
    global flag 
    
    if flag : return    
    if idx >= len(unknown) :
        flag = True
        pprint()
        return
    
    r, c = unknown[idx]    
    numberSet = rowCandidate[r] & colCandidate[c] & blockCandidate[r//3][c//3]
    for num in numberSet : 
        board[r][c] = num
        rowCandidate[r].remove(num)
        colCandidate[c].remove(num)
        blockCandidate[r//3][c//3].remove(num)
        find(idx+1)
        
        board[r][c] = 0
        rowCandidate[r].add(num)
        colCandidate[c].add(num)
        blockCandidate[r//3][c//3].add(num)
find(0)