[백준] 2239번 스도쿠 (파이썬, DFS)

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

2239번: 스도쿠

스도쿠 조아~

익숙한 기법을 좋아하다보니 이번에도 DFS로 구현했다.

사실 BFS로 하기에는 뭔가 이상한 것 같아서 그런 것도 있다.

 

원래 스도쿠 푸는 걸 좋아했는데 무지성으로 다 때려 박아서 풀지만 나보다 빨리 푸는 코드를 보면서 씁슬한 마음이 들었다.

 

문제 접근은 간단하다.

규칙에 맞는 숫자가 없다면 백트래킹 하도록 구현하면 그만이다.

 

 

def dfs(i):
    if i == len(arr):
        ppp()
        sys.exit(0)
    x = arr[i][0]
    y = arr[i][1]
    b = box(x, y)
    for k in range(1, 10):
        if not k in board[x]:
            c = 0
            for n in range(9):
                if k == board[n][y]:
                    c = 1
                    break
            if c == 1:
                continue
            if not k in nop[b]:
                board[x][y] = k

                nop[b].append(k)
                dfs(i+1)
                board[x][y] = 0
                nop[b].remove(k)

 

dfs 자체는 이런 식으로 구현했다.

여기서 핵심은 arr과 box이다.

3*3 크기의 박스에서 숫자가 중복되는지 확인하는 과정은 매번 진행하면 번거롭다.

그렇기 때문에 사전에 9개의 박스에 각각 들어있는 숫자를 미리 배열로 넣어서 nop에 저장했다.

이렇게 하면 k라는 상수가 박스 안에 있는지 검증하는 것은 현재 x,y 좌표에 해당하는 상자의 번호를 알아오고 그 번호에 해당하는 상자에 중복되는 숫자가 있는지만 찾으면 된다. 

if not k in nop[b]

이런 식으로 깔끔하게 정리가 가능하다.

def box(x, y):
    if x//3 == 0:
        if y//3 == 0:
            return 0
        elif y//3 == 1:
            return 1
        elif y//3 == 2:
            return 2
    if x//3 == 1:
        if y//3 == 0:
            return 3
        elif y//3 == 1:
            return 4
        elif y//3 == 2:
            return 5
    if x//3 == 2:
        if y//3 == 0:
            return 6
        elif y//3 == 1:
            return 7
        elif y//3 == 2:
            return 8

 

몇 번째 상자인지 구하는 방법은 3으로 나눴을때의 몫에 있다.

1~9로 생각하면 안된다.

인덱스 배열 그자체로 생각하는 편이 더 쉽다.

0~2는 3으로 나눌때 0이고 3~5는 1, 6~8은 2인 점을 고려해서 좌표값을 압축해서 표시할 수 있다.

 

board = [list(map(int, list(str(sys.stdin.readline().rstrip()))))
         for _ in range(9)]
arr = []
nop = [[], [], [], [], [], [], [], [], []]
for i in range(9):
    for j in range(9):
        if board[i][j] != 0:
            if i//3 == 0:
                if j//3 == 0:
                    nop[0].append(board[i][j])
                elif j//3 == 1:
                    nop[1].append(board[i][j])
                elif j//3 == 2:
                    nop[2].append(board[i][j])
            elif i//3 == 1:
                if j//3 == 0:
                    nop[3].append(board[i][j])
                elif j//3 == 1:
                    nop[4].append(board[i][j])
                elif j//3 == 2:
                    nop[5].append(board[i][j])
            elif i//3 == 2:
                if j//3 == 0:
                    nop[6].append(board[i][j])
                elif j//3 == 1:
                    nop[7].append(board[i][j])
                elif j//3 == 2:
                    nop[8].append(board[i][j])
        else:
            arr.append([i, j])

nop 또한 입력 받은 후 바로 생성해 줌으로 탐색을 계속 돌릴 필요를 없애준다.

 

 

그리고 가장 중요한 핵심은 dfs에서 arr과 i이다.(이 부분은 사실 for문을 써도 되지 않았을까 싶다)

board의 좌표를 계속 올려가면서 91개의 칸을 탐색하는 것이 아닌 0인 칸. 즉, nop를 정의할 때 함께 arr도 정의하여 비어있는 칸의 좌표를 arr에 넣어 줌으로써 빈 칸만 루프를 돌려가며 탐색하도록 했다.

이 부분이 가장 중요했던 것 같다.

 

하지만 python3 로는 시간초과임으로 pypy를 활용했다..