[백준] 2580번 : 스도쿠 - JAVA [자바]

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

---

• 문제

 

 

 

N-Queen 문제를 풀었다면 이 문제 또한 접근 방법만 잘 이해한다면 매우 쉽게 풀 수 있는 문제다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

 

스도쿠를 한 번쯤은 모두 접해보셨을 것이라 생각한다. 같은 행과 열에 겹치지 않으면서 3×3 행렬 안에서도 겹치면 안된다. 즉, 이 규칙을 토대로 조건문을 만들어야 한다는 것은 누구나 알 것이다.

 

이전 문제처럼 재귀호출부와 조건 검사 함수, 이렇게 두 개를 구성하도록 하자. 최대한 이해하기 쉽게 주석과 함께 설명하도록 하겠다.

 

 

문제 풀이 접근 방식은 위의 예제를 토대로 설명하겠다.

 

위와 같이 주어졌을 때 (빈칸은 0 으로 주어진다.) 2차원 배열을 활용한다.

즉, int[][] 배열을 사용 할 것인데, 첫 번째 인덱스는 행을, 두 번째 인덱스는 열을 의미한다. ( int[row][col] )

그리고 [0][0] 을 왼쪽 위를 기준으로 할 것이니 이 기준을 이해하고 넘어가자.

 

 

 

[조건식]

 

스도쿠 규칙은 간단하다. 해당 칸에 속한 3×3 배열 안에서 숫자가 겹치지 않으며, 해당 칸과 같은 행과 열 또한 숫자가 겹치지 않아야 한다. 즉, 어떤 값이 해당 칸에 들어갈 수 있는지 여부를 판별해야된다. 이때 탐색하려는 값을 value 라고 정하고 조건식을 만들면 세 가지 조건식을 만들 수 있다.

 

먼저 위 예시를 토대로 (0, 0)부터 검사하도록 해보자.

 

1. 같은 행에 있는 열 원소 중에 겹치는 수가 있는지를 검사한다.

조건식으로 하면 아래와 같을 것이다.

public static boolean possibility(int row, int col, int value) {

	// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사.
	for (int i = 0; i < 9; i++) {
		if (arr[row][i] == value) {
			return false;
		}
	}
	return true;
}

 

 

 

 

2. 같은 열에 있는 행 원소 중에 겹치는 수가 있는지를 검사한다.

조건식으로 하면 아래와 같다.

public static boolean possibility(int row, int col, int value) {
    
	// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
	for (int i = 0; i < 9; i++) {
		if (arr[i][col] == value) {
			return false;
		}
	}
	return true;
}

 

 

 

 

 

3. 해당 위치에 속한 3×3 칸에 중복되는 수가 있는지를 검사한다.

조건식은 다음과 같다.

public static boolean possibility(int row, int col, int value) {

	// 3*3 칸에 중복되는 원소가 있는지 검사
    
	int set_row = (row / 3) * 3;	// value가 속한 3x3의 행의 첫 위치
	int set_col = (col / 3) * 3;	// value가 속한 3x3의 열의 첫 위치

	for (int i = set_row; i < set_row + 3; i++) {
		for (int j = set_col; j < set_col + 3; j++) {
			if (arr[i][j] == value) {
				return false;
			}
		}
	}

	return true;
}

 

여기서 3×3의 위치는 9×9 사이즈에서 3개로 나누면 총 9칸이 생기는데, 각 칸의 위치는 왼쪽 위를 기준으로 할 것이기 때문에 나눗셈을 통해 나머지를 버린 뒤 다시 3을 곱하여 0, 3, 6 중 하나가 나올 수 있도록 한다. 즉, 9개의 칸의 첫 원소의 위치는 다음 9개 중 하나다. ( [0][0], [0][3], [0][6], [3][0], [3][3], [3][6], [6][0], [6][3], [6][6] )

 

 

위 3가지 조건을 모두 통과해야 해당 value 값이 해당 칸에 수가 될 수 있게 된다. 즉, 위 3개의 조건문을 하나로 합치면 다음과 같다. 

public static boolean possibility(int row, int col, int value) {

	// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사.
	for (int i = 0; i < 9; i++) {
		if (arr[row][i] == value) {
			return false;
		}
	}
    
	// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
	for (int i = 0; i < 9; i++) {
		if (arr[i][col] == value) {
			return false;
		}
	}

	// 3*3 칸에 중복되는 원소가 있는지 검사
    
	int set_row = (row / 3) * 3;	// value가 속한 3x3의 행의 첫 위치
	int set_col = (col / 3) * 3;	// value가 속한 3x3의 열의 첫 위치

	for (int i = set_row; i < set_row + 3; i++) {
		for (int j = set_col; j < set_col + 3; j++) {
			if (arr[i][j] == value) {
				return false;
			}
		}
	}

	return true;	// 중복되는 것이 없을 경우 true 반환
}

 

 

 

 

그리고 배열을 (0,0) 부터 순회하며 만약 탐색하는 칸의 값이 0(빈칸)일 경우 반복문을 통해 1 ~ 9 까지의 수들 중 위의 possibility 함수를 통해 만족하게 된다면 재귀호출을 해주는 것이다.

 

 

그럼 위의 내용을 기반으로 코드를 짜보자. 

 

참고로 재귀 호출하면서 모든 값이 다 채워지게 된다면 배열을 출력한 뒤 시스템을 종료해야한다. 아니면 여러개의 스도쿠가 출력된다. (문제에서 나와있듯이 경우의 수가 많을 경우 '한 개'만 출력하라고 명시되어있다) 이 때 시스템을 종료하는 방법은 System.exit(0) 를 사용하면 된다.

 

 

 

 

 

 

 

 

 

 

---

• 3가지 방법을 사용하여 풀이한다.

 

알고리즘은 위에서 설명했던 방식 그대로 사용할 것이다. 다만 입출력에서 차이를 두어 각 방법 별 성능차를 보도록 하자.

 

1 . Scanner + System.out.print 반복출력

2 . Scanner + StringBuilder

3. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + System.out.print 반복출력]

 

import java.util.Scanner;

public class Main {

	public static int[][] arr = new int[9][9];

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				arr[i][j] = in.nextInt();
			}
		}

		sudoku(0, 0);

	}

	public static void sudoku(int row, int col) {

		// 해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
		if (col == 9) {
			sudoku(row + 1, 0);
			return;
		}

		// 행과 열이 모두 채워졌을 경우 출력 후 종료
		if (row == 9) {
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					System.out.print(arr[i][j] + " ");
				}
				System.out.println();
			}

			// 출력 뒤 시스템을 종료한다.
			System.exit(0);
		}

		// 만약 해당 위치의 값이 0 이라면 1부터 9까지 중 가능한 수 탐색
		if (arr[row][col] == 0) {
			for (int i = 1; i <= 9; i++) {
				// i 값이 중복되지 않는지 검사
				if (possibility(row, col, i)) {
					arr[row][col] = i;
					sudoku(row, col + 1);
				}
			}
			arr[row][col] = 0;
			return;
		}

		sudoku(row, col + 1);

	}

	public static boolean possibility(int row, int col, int value) {

		// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (arr[row][i] == value) {
				return false;
			}
		}

		// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (arr[i][col] == value) {
				return false;
			}
		}

		// 3*3 칸에 중복되는 원소가 있는지 검사
		int set_row = (row / 3) * 3; // value가 속한 3x3의 행의 첫 위치
		int set_col = (col / 3) * 3; // value가 속한 3x3의 열의 첫 위치

		for (int i = set_row; i < set_row + 3; i++) {
			for (int j = set_col; j < set_col + 3; j++) {
				if (arr[i][j] == value) {
					return false;
				}
			}
		}

		return true; // 중복되는 것이 없을 경우 true 반환
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

앞서 말했듯 StringBuilder 가 아니라 System.out.print(arr[i] + " "); 로 하게되면 시간초과가 나므로 주의하자.

StringBuilder 대신 BufferedWriter를 써도 된다.

 

 

---

- 방법 2 : [Scanner + StringBuilder]

 

 

 

배열을 출력할 때 좀 더 효율적으로 출력하기 위해 하나의 문자열로 이어준 뒤, 한 번에 출력하는 방법이다. 이를 위해 StringBuilder 를 사용할 것이다.

 

 

import java.util.Scanner;

public class Main {

	public static int[][] arr = new int[9][9];

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				arr[i][j] = in.nextInt();
			}
		}

		sudoku(0, 0);

	}

	public static void sudoku(int row, int col) {

		// 해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
		if (col == 9) {
			sudoku(row + 1, 0);
			return;
		}

		// 행과 열이 모두 채워졌을 경우 출력 후 종료
		if (row == 9) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(arr[i][j]).append(' ');
				}
				sb.append('\n');
			}
			System.out.print(sb);
			// 출력 뒤 시스템을 종료한다.
			System.exit(0);
		}

		// 만약 해당 위치의 값이 0 이라면 1부터 9까지 중 가능한 수 탐색
		if (arr[row][col] == 0) {
			for (int i = 1; i <= 9; i++) {
				// i 값이 중복되지 않는지 검사
				if (possibility(row, col, i)) {
					arr[row][col] = i;
					sudoku(row, col + 1);
				}
			}
			arr[row][col] = 0;
			return;
		}

		sudoku(row, col + 1);

	}

	public static boolean possibility(int row, int col, int value) {

		// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (arr[row][i] == value) {
				return false;
			}
		}

		// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (arr[i][col] == value) {
				return false;
			}
		}

		// 3*3 칸에 중복되는 원소가 있는지 검사
		int set_row = (row / 3) * 3; // value가 속한 3x3의 행의 첫 위치
		int set_col = (col / 3) * 3; // value가 속한 3x3의 열의 첫 위치

		for (int i = set_row; i < set_row + 3; i++) {
			for (int j = set_col; j < set_col + 3; j++) {
				if (arr[i][j] == value) {
					return false;
				}
			}
		}

		return true; // 중복되는 것이 없을 경우 true 반환
	}

}

 

 

 

 

출력이 그렇게 많은 편은 아니라 성능이 유의미하게 차이가 있을련지는 모르겠지만,, 필자는 어지간한 출력에는 대부분 StringBuilder 나 BufferedWriter 을 쓰는 편이다.

 

물론 StringBuilder 대신 BufferedWriter를 써도 되니, 한 번 시도해보는 것도 나쁘지 않다.

 

 

---

- 방법 3 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 바꾼 방법이다. 이 때 문자열 분리를 해주어야 할 필요가 있는데, 문자열 분리는 StringTokenizer 을 사용 할 것이다. 물론 이 방법 말고, charAt(j*2) 형식으로 바꾸어 해당 문자에 '0' 이라는 문자를 뺀 값을 넣어주어도 된다. 이는 여러분들이 선호하는 방식대로 해주면 된다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static int[][] arr = 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++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		sudoku(0, 0);

	}

	public static void sudoku(int row, int col) {

		// 해당 행이 다 채워졌을 경우 다음 행의 첫 번째 열부터 시작
		if (col == 9) {
			sudoku(row + 1, 0);
			return;
		}

		// 행과 열이 모두 채워졌을 경우 출력 후 종료
		if (row == 9) {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					sb.append(arr[i][j]).append(' ');
				}
				sb.append('\n');
			}
			System.out.println(sb);
			// 출력 뒤 시스템을 종료한다.
			System.exit(0);
		}

		// 만약 해당 위치의 값이 0 이라면 1부터 9까지 중 가능한 수 탐색
		if (arr[row][col] == 0) {
			for (int i = 1; i <= 9; i++) {
				// i 값이 중복되지 않는지 검사
				if (possibility(row, col, i)) {
					arr[row][col] = i;
					sudoku(row, col + 1);
				}
			}
			arr[row][col] = 0;
			return;
		}

		sudoku(row, col + 1);

	}

	public static boolean possibility(int row, int col, int value) {

		// 같은 행에 있는 원소들 중 겹치는 열 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (arr[row][i] == value) {
				return false;
			}
		}

		// 같은 열에 있는 원소들 중 겹치는 행 원소가 있는지 검사
		for (int i = 0; i < 9; i++) {
			if (arr[i][col] == value) {
				return false;
			}
		}

		// 3*3 칸에 중복되는 원소가 있는지 검사
		int set_row = (row / 3) * 3; // value가 속한 3x3의 행의 첫 위치
		int set_col = (col / 3) * 3; // value가 속한 3x3의 열의 첫 위치

		for (int i = set_row; i < set_row + 3; i++) {
			for (int j = set_col; j < set_col + 3; j++) {
				if (arr[i][j] == value) {
					return false;
				}
			}
		}

		return true; // 중복되는 것이 없을 경우 true 반환
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 20835695  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 20835691  -  방법 2 : Scanner + StringBuilder

채점 번호 : 20835688  -  방법 1 : Scanner + System.out.print 반복 출력

 

 

 

---

• 정리

 

이 번 문제 또한 그리 어려운 문제는 아니였다. 그런데 정답 비율이 높지 않은 것을 보면 아마 재귀호출을 잘못하지 않았을까 싶다. 이러한 백트래킹 문제는 '조건'과 '재귀'를 정확하게 작성해주지 않으면 자칫 재귀가 깊어지거나 이상하게 튀어버릴 수 있기 때문에 반드시 구상을 먼저 정확하게 해야 한다.

 

가장 추천하는 방법은 디버깅을 해보는 것이 좋다.

 

혹여 이 문제가 이해가 되지 않거나 설명이 부족한 부분이 있다면 댓글 남겨주시면 최대한 빠르게 답변드리겠다.