[Java+Python]2580번, 스도쿠

목차

 

문제

 

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 

이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 

게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

 

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

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

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

첫째 줄 빈칸에는 1이 들어가야 한다.

 

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

가운데 빈칸에는 3이 들어가야 한다.

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

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때,

모든 빈칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

입력

 

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 

스도쿠 판의 빈칸의 경우에는 0이 주어진다. 

스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

 

출력

 

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

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

 

풀이

 

대놓고 PyPy3으로 풀라고 되어있다. 무시하고 온갖 방법으로 파이썬 3에서 통과시키려 했으나 실패.

 

주어진 로직으로 반드시 풀리는 경우만 주어진다고 했으니 로직은 그다지 어렵지 않다.

 

먼저 주어진 문제를 전역변수로 선언한 이차원 배열 board[9][9]에 저장한다.

 

다음으로 sudoku() 메서드를 선언하면서 백트래킹 기법으로 다음과 같이 풀어나간다.

 

1. 이차원 배열을 순회하며 현재 위치가 0인지 확인한다. 0이 아니라면 다음열로 이동한다.
2. 0일 경우 1부터 9까지의 숫자를 넣으며 isPossible() 메서드를 통해 해당 위치에 유효한 숫자인지 확인한다.
   1. isPossible() 메서드의 경우 먼저 rowStart와 colStart를 계산한다.
      예를 들어 (row, col)이 (4, 7)인 경우 (rowStart, colStart)는 (3, 6)이 된다(<그림 1> 참고).
   2. 이어서 반복문을 통해 해당 위치에 주어진 숫자가 들어가는지 검사하는데,
      이 경우 현재 행, 열, 그리고 위에서 시작점을 뽑아낸 작은 사각형에서 같은 숫자가 있는지 확인하게 된다.
   3. 위 조건 중 하나라도 걸린다면 현재 위치에는 주어진 숫자를 넣을 수 없기 때문에 false를 반환하고,
      세 가지 조건 모두를 만족하지 않는다면, 그러니까 같은 숫자가 없다면 true를 반환한다.
3. 이어서 다음 위치인 sudoku(row, col + 1)을 재귀 호출해 다음 열에 대한 경우의 수를 확인하며,
   모든 위치에 숫자가 채워졌다면 true를, 그렇지 않다면 해당 숫자를 다시 0으로 초기화하고 false를 반환한다.
4. row가 9에 도달하면, 즉 모든 칸에 숫자가 채워졌다면 printBoard()를 통해 정답을 출력하고 프로그램을 종료한다.

이와 같이 풀어가다 실패할 경우 처음으로 돌아와서 다시 시작해야 하기 때문에 시간이 많이 걸리게 된다.

 

Java

 

먼저 자바 코드이다. 위에서 정리한 알고리즘을 그대로 코드로 옮긴 것에 불과하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Prob2580_5 {

	static int[][] board = new int[9][9];

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		sudoku(0, 0);
	}

	private static boolean sudoku(int row, int col) {

		if (col == 9) {
			return sudoku(row + 1, 0);
		}

		if (row == 9) {
			printBoard();
			return true;
		}

		if (board[row][col] == 0) {
			for (int num = 1; num <= 9; num++) {
				if (isPossible(row, col, num)) {
					board[row][col] = num;
					if (sudoku(row, col + 1)) {
						return true;
					}
					board[row][col] = 0;
				}
			}
			return false;
		} else {
			return sudoku(row, col + 1);
		}
	}

	private static boolean isPossible(int row, int col, int num) {

		int rowStart = (row / 3) * 3;
		int colStart = (col / 3) * 3;

		for (int i = 0; i < 9; i++) {
			if (board[row][i] == num || board[i][col] == num || board[rowStart + (i / 3)][colStart + (i % 3)] == num) {
				return false;
			}
		}

		return true;
	}

	private static void printBoard() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				sb.append(board[i][j]).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
}

 

Python

 

이어서 파이썬 코드이다. 같은 코드로 PyPy3은 통과하지만 Python3은 통과하지 못한다.

 

자바로 적은 위 코드를 파이썬 문법에 맞춰 번역한 코드라고 보면 된다.

import sys

lines = sys.stdin.readlines()
board = [list(map(int, line.rstrip().split())) for line in lines]


def is_possible(row, col, num):
    row_start = (row // 3) * 3
    col_start = (col // 3) * 3

    for i in range(9):
        if (
            board[row][i] == num
            or board[i][col] == num
            or board[row_start + (i // 3)][col_start + (i % 3)] == num
        ):
            return False
    return True


def sudoku(row, col):
    if col == 9:
        return sudoku(row + 1, 0)

    if row == 9:
        output = '\n'.join([' '.join(map(str, row)) for row in board])
        print(output)
        return True

    if board[row][col] == 0:
        for num in range(1, 10):
            if is_possible(row, col, num):
                board[row][col] = num
                if sudoku(row, col + 1):
                    return True
                board[row][col] = 0
        return False
    else:
        return sudoku(row, col + 1)


sudoku(0, 0)

 

Performance

 

파이썬의 경우 스크립트 언어의 특성까지 더해 메모리를 어마어마하게 잡아먹는 것을 확인할 수 있다.