[백준] 2580번 : 스도쿠 (python 파이썬)

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

 

스도쿠 체우기!

 

 

 

import sys
sys.setrecursionlimit(10 ** 8)
graph = []
for i in range(9):
    l = list(map(int , input().split(" ")))
    graph.append(l)

vst1 =[[False for i in range(9)] for j in range(9)] #i 번째 가로방향에 j가 있는지의 여부
vst2 =[[False for i in range(9)] for j in range(9)] #i 번째 세로 방향에 j 가 있는지의 여부
vst3 =[[False for i in range(9)] for j in range(9)] #i 번째 박스에 j 가 있는지 여부

for i in range(9):
    for j in range(9):
        if graph[i][j] != 0:
            vst1[i][graph[i][j]-1] = True
            vst2[j][graph[i][j]-1] = True
            vst3[(i//3)*3 + (j//3)][graph[i][j] -1] =True
    
def backtrack(x,y):
    if y == 9:
        y = 0
        x +=1
    if x == 9:
        for _ in graph:
            print(*_ )
        sys.exit(0)
        return
    
    if graph[x][y] == 0:
        for num in range(1,10):
            if vst1[x][num-1] == False and vst2[y][num-1] == False and vst3[(x//3)*3 + (y//3)][num-1] == False:
                vst1[x][num-1] = True
                vst2[y][num-1] = True
                vst3[(x//3)*3 + (y//3)][num-1] = True
                graph[x][y] = num
                backtrack(x,y+1)
                vst1[x][num-1] = False
                vst2[y][num-1] = False
                vst3[(x//3)*3 + (y//3)][num-1] = False
                graph[x][y] = 0
    else:
        backtrack(x,y+1)

                
backtrack(0,0)

 

 

위 문제는 풀면서 많은 생각을 할 수 있게 된 문제이다.

 

스도쿠 문제를 푸는 문제였는데, 전형적인 백트레킹 문제였다.

 

해당 문제는 백트레킹을 푸는 연습하는 데 정말 도움이 많이 되었던 것 같다.

 

특별한 아이디어나 이론이 필요하다긴 보다는, 문제를 푸는 방식을 코드로 구현하는 능력과

 

효율적으로 들어갈 수 있는 숫자를 찾는 방법 등이 필요했다.

 

 

스도쿠 문제는 가로, 세로, 한 박스 안에 숫자가 겹치지 않아야 한다.

 

1. 0,0 부터 8,8 까지 돌면서 만약 0을 만나면,

2. 그 자리를 기준으로 가능한 숫자를 넣고

3. 백트레킹을 돌리기만 하면 된다.

 

1번과 3번은 매우 간단해 보인다.

2번을 어떻게 구현해햐 할까?

 

 

 

 

 

우선 입력을 받는다.

graph = []

for i in range(9):

    l = list(map(int , input()))

    graph.append(l)

 

 

입력 받은 정보를 토대로 방문 정보를 담아둔다.

vst1 =[[False for i in range(9)] for j in range(9)] #i 번째 가로방향에 j가 있는지의 여부

vst2 =[[False for i in range(9)] for j in range(9)] #i 번째 세로 방향에 j 가 있는지의 여부

vst3 =[[False for i in range(9)] for j in range(9)] #i 번째 박스에 j 가 있는지 여부

 

vst1은 가로 방향 (열)을 기준으로 i번 째 열에 j라는 수가 있는지의 정보를 담는다.

 

vst2는 세로 방향 (행)을 기준으로 i 번째 행에 j라는 수가 있는지의 정보를 담는다.

 

vst3은 i번째 박스에 j라는 수가 있는지의 여부를 담는다.

 

1	2	3
4	5	6
7	8	9

 

스도쿠를 9개의 박스로 나누어 i 번째 박스에 j라는 수가 있는지 확인한다.

 

for i in range(9):

    for j in range(9):

        if graph[i][j] != 0:

            vst1[i][graph[i][j]-1] = True

            vst2[j][graph[i][j]-1] = True

            vst3[(i//3)*3 + (j//3)][graph[i][j] -1] =True

 

0,0 부터 8,8 까지 돌면서 현재 스도쿠가 비어있지 않으면 (0 이 아니면) 방문 정보를 채운다.

vst3 번은 

(0*3)+1	(0*3) +2	(0*3) +3
(1*3) +1	(1*3) +2	(1*3) +3
(2*3) +1	(2*3) +2	(2*3) +3

위의 관점으로 바라보면 쉽게 이해할 수 있을 것이다.

 

 

 

위의 방문 정보를 다 채웠다면..?

backtrack(0,0)

 

백트레킹을 시작해보자!

 

def backtrack(x,y):

    if y == 9:

        y = 0

        x +=1

    if x == 9:

        for _ in graph:

            print(*_ )

        sys.exit(0)

        return

   

    if graph[x][y] == 0:

        for num in range(1,10):

            if vst1[x][num-1] == False and vst2[y][num-1] == False and vst3[(x//3)*3 + (y//3)][num-1] == False:

                vst1[x][num-1] = True

                vst2[y][num-1] = True

                vst3[(x//3)*3 + (y//3)][num-1] = True

                graph[x][y] = num

                backtrack(x,y+1)

                vst1[x][num-1] = False

                vst2[y][num-1] = False

                vst3[(x//3)*3 + (y//3)][num-1] = False

                graph[x][y] = 0

    else:

        backtrack(x,y+1)

 

백트래킹에 들어가는 (0,0) 은 현재 위치를 말한다.

 

현재 위치가 만약 0이라면 가능한 숫자를 찾아서 넣으면 되고,

if graph[x][y] == 0:

        for num in range(1,10):

            if vst1[x][num-1] == False and vst2[y][num-1] == False and vst3[(x//3)*3 + (y//3)][num-1] == False:

                vst1[x][num-1] = True

                vst2[y][num-1] = True

                vst3[(x//3)*3 + (y//3)][num-1] = True

                graph[x][y] = num

                backtrack(x,y+1)

                vst1[x][num-1] = False

                vst2[y][num-1] = False

                vst3[(x//3)*3 + (y//3)][num-1] = False

                graph[x][y] = 0

 

1. 가능한 숫자는 1 부터 9까지 for문을 돌면서

2. 해당 숫자를 방문 정보와 비교해서, 방문하지 않았다면,

3. 방문처리를 하고, 집어 넣는다.

4. 그리고 다음 차례로 간다. -> backtrack(x,y+1)

5. 1부터 9까지의 수를 다 확인해야 하므로, 방문처리들을 다시 돌려놓고, 다음 숫자를 확인한다.

 

 

현재 위치가 0이 아니라면, 이미 숫자가 있는 것이므로, 다음으로 넘어가면 된다.

else:

        backtrack(x,y+1)

 

 

처음에는 2중 for문을 사용해서 구현하려고 했지만, 겹치는 계산이 존재하고, 구현에 어려움을 느꼈다.

 

따라서 직접 x, y 값을 넘기고, 초반에 인덱스 체크를 하는 형식으로 하고,

 

숫자만 확인하도록 코드 부분을 구분하니 더 수월하게 구현할 수 있었다.