백준 2580 파이썬 코드 답안

 

 

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

제한

• baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

 

 

문제 풀이

종료 조건이 정확하기 때문에 완전탐색에 백트래킹 기법을 적용하는 방식으로 풀었다. 백트래킹에 가장 중요한 것은 유망한 노드인지 확인하는 로직을 짜는 것이다. 유망한 노드인지 확인하는 로직만 짠다면, 그 후에는 DFS든 완전탐색이든 하면 되기 때문! 

유망한 노드인지 확인하는 조건은 아래 두 가지다.
첫번째 조건, 해당 노드에 이 값을 적었을 때, 가로, 세로 영역에 이 값이 없어야 한다.

def aaa(Y,X) :
    for next_y in range(0,9) :
        if Y != next_y :
            if my_list[Y][X] == my_list[next_y][X] :
                return False
    for next_x in range(0,9) :
        if X != next_x :
            if my_list[Y][next_x] == my_list[Y][X] :
                return False
    return bbb(Y,X)

두번째 조건, 해당 노드에 이 값을 적었을 때, 해당 노드가 있는 3*3 영역에 이 값이 없어야 한다. 

def bbb(Y,X) :
    center_x = (X//3)*3 + 1
    center_y = (Y//3)*3 + 1
    for i in range(center_x-1,center_x+2) :
        for j in range(center_y-1,center_y+2) :
            if j != Y and i != X :
                if my_list[j][i] == my_list[Y][X] :
                    return False
    return True

위의 유망성 노드 함수를 짠 후, 완전탐색에 적절히 아래와 같이 녹여주면 된다. 다만, 실행 시간이 좀 오래 걸려서... 뭔가 최적화를 해야하는데.. 좀 더 고민해봐야하겠다, 그 부분은..

import sys

# aaa 함수는 해당 인덱스의 세로,가로 영역을 살펴보는 것이 가장 큰 역할임.
# next_y 영역에서 현재 값인 Y,X에 저장된 인덱스와 같은 값이 있는지 없는지를 살펴봄
# 만약 여기서 같은 값이 있다면 False로 바로 종료함.
# next_y 통과 시, next_x에 대해서도 동일한 로직으로 검사함
# 여기까지 검사를 했을 때, 문제가 없다면 3*3 영역에서도 문제가 없는지 확인하는 bbb 함수로 넘어감

def aaa(Y,X) :
    for next_y in range(0,9) :
        if Y != next_y :
            if my_list[Y][X] == my_list[next_y][X] :
                return False
    for next_x in range(0,9) :
        if X != next_x :
            if my_list[Y][next_x] == my_list[Y][X] :
                return False
    return bbb(Y,X)

                    
# bbb 함수는 3*3 영역에 문제가 있는지 없는지 확인하는 함수임.
# 주어진 Y,X 값으로 3*3 영역의 가운데 값을 확인함 
# 가운데 값을 기준으로 이중 포문을 돌려 3*3 영역을 완전탐색해서 문제가 없는지 확인함.
                    
def bbb(Y,X) :
    center_x = (X//3)*3 + 1
    center_y = (Y//3)*3 + 1
    for i in range(center_x-1,center_x+2) :
        for j in range(center_y-1,center_y+2) :
            if j != Y and i != X :
                if my_list[j][i] == my_list[Y][X] :
                    return False
    return True

# 스도쿠 종료를 위한 함수
# 이 맵 안에 남은 0이 있는지 확인해주고, 0이 없으면 스도쿠 게임 완료된 것으로 간주하고 EXIT

def check() :
    for i in range(9):
        for j in range(9):
            if my_list[i][j] == 0 :
                return False
    return True


# 스도쿠 메인함수
# 0,0부터 0이 있는지 확인한다
# 0이 있으면 123456789를 차례대로 넣어본다.
# 차례대로 넣어본 후, aaa(i,j) 함수 호출로 [i][j] 라는 곳에 해당 값이 들어갈 수 있는 가지치기를 한다
# 가지치기에서 살아남은 가지라면, 재귀를 통해서 다음 단계로 넘어간다.
# 가지치기에서 하나도 살아남은 가지가 없다면 바로 return 한다.
# i==8, j==8이 되었을 때(모두 완료되었을 때), 정말로 스도쿠가 완료되었는지 check 함수로 체크한다.
# 완료된 것이 확인되면 스도쿠를 print 해주고, exit()로 코드 종료함.

def sk(my_list) :
    for i in range(9) :
        for j in range(9) :
            if my_list[i][j] == 0 :
                for num in range(1,10) :
                    my_list[i][j] = num
                    if aaa(i,j) :
                        sk(my_list)
                my_list[i][j] = 0
                return
    if check() :
        for k in range(9):
            print(' '.join(map(str, my_list[k])))
        exit()


my_list = []
for i in range(9) :
    my_list.append(list(map(int,sys.stdin.readline().split())))
sk(my_list)