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

# 입력 부분
import sys

input = sys.stdin.readline

tmp=[input().strip() for _ in range(9)]
board=[[0]*9 for _ in range(9)]
for r in range(9):
    for c in range(9):
        board[r][c]=int(tmp[r][c])
        
# 출력 부분
for r in range(9):
    for c in range(9):
        print(board[r][c],  end='')
    print()​

2580번: 스도쿠

 

2239번과 2580번의 코드는 거의 유사하다. 하지만 조금 더 일반적인 2580을 먼저 다룬 후 2239를 풀어보겠다.

 

2580 >>

 

스도쿠는 9*9 판에서 다음 조건을 모두 만족시키면 되는 게임이다.

1. 가로 한 줄에는 1 부터 9까지 숫자가 각각 한 번씩만 들어가야 한다.
2. 세로 한 줄에는 1 부터 9까지 숫자가 각각 한 번씩만 들어가야 한다.
3. 네모 칸 하나(총 9개)에는 1 부터 9까지 숫자가 각각 한 번씩만 들어가야 한다.

즉 스도쿠 문제를 품에 있어서 시행 착오가 반드시 생긴다. 왜냐하면 빈칸 하나당 들어갈 수 있는 숫자 후보가 1개 이상이기 때문이다. 그래서 결국 최종 정답도 여러 개가 생길 가능성도 없진 않다. 

 

백트래킹 알고리즘을 사용해서 문제를 풀어보자.

 

일단 틀을 짜주면 다음과 같다.

import sys
input = sys.stdin.readline

# 입력
board=[]
for _ in range(9):
    board.append([*map(int, input().split())])
# 3*3 확인, 가로, 세로 확인
def check(board, row, col, num):
    ...
# 백트래킹
def solve(board):
    ...
solve(board)
# 출력
for row in board:
    print(*row)

이제 solve 함수를 구축해보자.

우리는 81개의 숫자들을 하나하나 검사해서 0인지 일단 확인해야 한다. 즉 아래와 같은 코드가 먼저 들어가야 함을 알 수 있다.

# 백트래킹
def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c]==0:

만약 해당 칸이 0 임이 확인되면 이제 1~9의 숫자 중에서 어떤 숫자가 와야 할지 결정해야 한다. 따라서 해당 칸에 숫자 num이 들어가기 적절한지 알려주는 함수 check()를 사용해주어야 한다. 즉 if board [r][c]==0: 이후의 코드는 아래와 같다

 

# 백트래킹
def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c]==0:
                for num in range(1, 10):
                    if check(board, r, c, num):

이제 check 함수를 만들어주자. 현재 주시하고 있는 81개의 칸 중 한 개의 칸에 대한 행 정보(r), 열 정보(c)를 넘겨준다.

우리가 check 함수를 통해 False를 리턴할 경우는 다음 세 가지이다.

1. 가로 줄에 num이 이미 있다.
2. 세로줄에 num이 이미 있다.
3. 3*3짜리 칸에 num이 이미 있다.

위 세 가지 경우를 모두 만족시키지 않으면 True를 리턴한다.

# 3*3 확인, 가로, 세로 확인
def check(board, row, col, num):
    if num in board[row]: # 가로줄에 num있는지 확인
        return False
    if num in [board[r][col] for r in range(9)]: # 세로줄에 num있는지 확인
        return False
    # 3*3짜리 칸에 대해 탐색을 하기 위해 몫 연산
    start_row=(row//3)*3
    start_col=(col//3)*3
    for r in range(3):
        for c in range(3):
            if board[r+start_row][c+start_col]==num:
                return False
    return True

 

이어서 check가 True를 반환하는 경우에 대해 생각해 보자. check가 True를 반환했다는 뜻은 board [r][c]에 num이 들어가도 된다는 뜻이다. 즉 아래와 같이 백트래킹 코드를 확장시키면 된다.  

# 백트래킹
def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c]==0:
                for num in range(1, 10):
                    if check(board, r, c, num):
                        board[r][c]=num
                        if solve(board):
                            return True
                        board[r][c]=0
                return False
    return True # 81개의 칸을 성공적으로 완수 했으면 True 리턴
    # 이 마지막 줄은 결국 if solve(board)가 참이 되게끔 한다. 즉 solve함수의 종료

 

최종 코드 >>

import sys
input = sys.stdin.readline

# 입력
board=[]
for _ in range(9):
    board.append([*map(int, input().split())])
# 3*3 확인, 가로, 세로 확인
def check(board, row, col, num):
    if num in board[row]:
        return False
    if num in [board[r][col] for r in range(9)]:
        return False
    start_row=(row//3)*3
    start_col=(col//3)*3
    for r in range(3):
        for c in range(3):
            if board[r+start_row][c+start_col]==num:
                return False
    return True


# 백트래킹
def solve(board):
    for r in range(9):
        for c in range(9):
            if board[r][c]==0:
                for num in range(1, 10):
                    if check(board, r, c, num):
                        board[r][c]=num
                        if solve(board):
                            return True
                        board[r][c]=0
                return False
    return True


solve(board)
# 출력
for row in board:
    print(*row)

 

2239 >>

 

입력받는 방식만 아래와 같이 바꾸고 출력 형식도 아래와 같이 바꾸면 정답처리가 된다.

# 입력 부분 
import sys

input = sys.stdin.readline

tmp=[input().strip() for _ in range(9)]
board=[[0]*9 for _ in range(9)]
for r in range(9):
    for c in range(9):
        board[r][c]=int(tmp[r][c])
        
# 출력 부분
for r in range(9):
    for c in range(9):
        print(board[r][c],  end='')
    print()

하지만 2239 문제는 좌측 상단에서 우측 하단으로 읽어 나갈 때 사전식으로 앞서는 것(작은 수가 가장 앞에 오게끔)을 출력하라고 했는데 어째서 우리가 2580을 풀면서 만들었던 코드를 그대로 사용해도 되는 것인가?

 

그 이유는 for num in range(1, 10):에 숨어 있다. 작은 숫자부터 board에 먼저 넣어 보고 백트래킹을 돌리기 때문에 저절로 작은 숫자가 앞에 오게 되는 것일 뿐이다.