백준 2580번 스도쿠 파이썬 풀이

 

문제

 

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

나머지 빈 칸을 채우는 방식은 다음과 같다. ~ 이하 생략

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

---

정답 코드

#스도쿠
import sys
sdoku = []
blank = []
for i in range(9):
    sdoku.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(9):
    for j in range(9):
        if(sdoku[i][j]==0):
            blank.append((i,j))
        

def isRowPromising(x,a):
    for i in range(9):
        if(sdoku[x][i] == a):
            return False
    return True

def isColPromising(y,a):
    for i in range(9):
        if(sdoku[i][y] == a):
            return False
    return True

def isRectanglePromising(x,y,a):
    nx = x//3 * 3
    ny = y//3 * 3
    for i in range(3):
        for j in range(3):
            if(a == sdoku[nx+i][ny+j]):
                return False
    return True

def dfs(idx):
    if(idx == len(blank)):
        for i in range(9):
            print(*sdoku[i])
        exit(0)

    x = blank[idx][0]
    y = blank[idx][1]
    for i in range(1,10):
        
        if(isRowPromising(x,i) and isColPromising(y,i) and isRectanglePromising(x,y,i)):
            sdoku[x][y] = i
            dfs(idx+1)
            sdoku[x][y] = 0

dfs(0)

풀이 과정

 

1. 탈출조건 설계

def dfs(idx):
    if(idx == len(blank)):
        for i in range(9):
            print(*sdoku[i])
        exit(0)

dfs 의 깊이가 blank의 길이와 같을 때는 모든 조건을 만족하여 sdoku의 숫자가 채워질 때입니다.

 

 

2.promsing 조건 설계

def isRowPromising(x,a):
    for i in range(9):
        if(sdoku[x][i] == a):
            return False
    return True

def isColPromising(y,a):
    for i in range(9):
        if(sdoku[i][y] == a):
            return False
    return True

for 문이 돌면서  index [0]~[8] 까지 즉, 가로 세로로 돌면서 체크합니다.

만약 같은 값이 그 줄(가로줄이든 세로줄이든)에 존재하면  False를 return 하고 , for 문을 모두 돌고 나서도 같은 값이 없으면 True 를 return 합니다.

 

def isRectanglePromising(x,y,a):
    nx = x//3 * 3
    ny = y//3 * 3
    for i in range(3):
        for j in range(3):
            if(a == sdoku[nx+i][ny+j]):
                return False
    return True

예를들어 blank 의 값이 (1,4)인 경우  아래와 같은  사각형에서 조건을 탐색합니다.

(0,4)	(0,5)	(0,6)
(1,4)	(1,5)	(1,6)
(2,4)	(2,5)	(2,6)

3 * 3 이라는 점에서 3의 몫을 활용하였습니다.

 

 

배운점 &&  공부방향 설정

1. 직관적으로는 이해가 되었는데, parameter로 무엇을 넣어야하는지 헷갈렸음.

 -> 구현적인 실력의 부족이 원인인 것으로 판단되므로 문제를 많이 풀어보는 수밖에 없다.

 

2. 직사각형 promising 조건을 어떻게 할지 생각이 나지 않음

-> 3 * 3 같은 경우 몫과 나머지를 활용하자.

 

3. 백트레킹 문제의 풀이 구조 설계는 거의 비슷하다. 

 -> 문제를 풀 때 promising 조건을 어떻게 설계할 지 고민하는 연습을 하자.