알고리즘/99Club
99클럽 코테 스터디 35일차 TIL + 스도쿠 (백트레킹)
dami97
2024. 8. 25. 22:29
반응형
소개
- 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
- TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
- 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.
문제 & 키워드
- 백준 - 스도쿠 (문제 링크)
- 백트래킹
문제 설명
스도쿠는 9x9 격자판에서 1부터 9까지의 숫자를 채워넣는 퍼즐 게임입니다. 이 게임의 규칙은 다음과 같습니다:
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.
- 굵은 선으로 구분된 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 합니다.
초기 스도쿠 판에 쓰여진 숫자들이 주어질 때, 빈 칸을 규칙에 맞게 채워서 스도쿠를 완성하는 프로그램을 작성하세요. 여러 개의 해답이 있을 수 있지만, 그 중 하나만 출력하면 됩니다.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 초기 스도쿠판의 각 줄에 쓰여 있는 숫자가 주어집니다. 빈 칸의 경우 0이 주어집니다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 출력합니다.
입출력 예
예제 입력 1
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0예제 출력 1
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1문제 접근
- 문제 이해
- 스도쿠 퍼즐은 빈 칸(0)을 규칙에 맞게 채우는 것입니다.
- 가로, 세로, 3x3 박스의 규칙에 맞게 1부터 9까지의 숫자를 채워넣어야 합니다.
- 백트래킹을 통해 가능한 모든 숫자를 시도해보고, 규칙에 맞는 경우 다음 칸으로 진행합니다.
- 풀이 방법
- 백트래킹(Backtracking)을 이용해 빈 칸을 채워나갑니다.
- 각 칸에 1부터 9까지의 숫자를 시도하며, 가로, 세로, 3x3 박스 규칙을 만족하는지 확인합니다.
- 규칙을 만족하는 경우 해당 숫자를 채우고 다음 칸으로 이동합니다.
- 만약 모든 칸이 채워지면 스도쿠를 출력하고 프로그램을 종료합니다.
풀이 - Java 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static int[][] board = new int[9][9];
private static int boardLength = 9;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for (int i = 0; i < boardLength; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < boardLength; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
sudoku(0, 0);
br.close();
}
private static void sudoku(int row, int col) {
if (col == boardLength) {
sudoku(row + 1, 0);
return;
}
// 행과 열이 모두 채워졌을 경우 출력 후 종료
if (row == boardLength) {
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);
// 출력 뒤 시스템을 종료한다.
System.exit(0);
}
// 만약 해당 위치의 값이 0 이라면 1부터 9까지 중 가능한 수 탐색
if (board[row][col] == 0) {
for (int i = 1; i <= 9; i++) {
// i 값이 중복되지 않는지 검사
if (possibility(row, col, i)) {
board[row][col] = i;
sudoku(row, col + 1);
}
}
board[row][col] = 0; // 해결하지 못하면 다시 돌아와서 0 으로 세팅후 해결못한 백트레킹
return;
}
sudoku(row, col + 1);
}
private static boolean possibility(int row, int col, int value) {
// 가로 검사
for (int i = 0; i < boardLength; i++) {
if(board[row][i] == value){
return false;
}
}
// 세로 검사
for (int i = 0; i < boardLength; i++) {
if(board[i][col] == value){
return false;
}
}
// 3*3 칸 검사
int row3 = (row / 3) * 3;
int col3 = (col / 3) * 3;
for (int i = row3; i < row3 + 3; i++) {
for (int j = col3; j < col3 + 3; j++) {
if(board[i][j] == value){
return false;
}
}
}
return true;
}
}풀이 설명
- 초기화
- 9x9 크기의 스도쿠 보드를 입력받아 초기화합니다. 이후 백트래킹을 통해 빈 칸을 채우기 시작합니다.
- 백트래킹을 이용한 빈 칸 채우기
- sudoku(int row, int col) 메서드는 현재 위치 (row, col)에 대해 가능한 숫자를 탐색하여 보드를 채웁니다.
- 보드의 끝에 도달하면 채워진 결과를 출력하고 프로그램을 종료합니다.
- 빈 칸에 대해서는 1부터 9까지의 숫자를 시도하며, 규칙에 맞는 숫자가 발견되면 그 숫자를 채우고 다음 칸으로 넘어갑니다.
- 가능한 숫자 검토
- possibility(int row, int col, int value) 메서드를 통해 특정 위치에 숫자를 채울 수 있는지 확인합니다.
- 가로, 세로, 3x3 박스를 모두 검사하여 해당 숫자가 중복되지 않으면 true를 반환하고, 중복되면 false를 반환합니다.
- 결과 출력 및 종료
- 모든 칸이 채워지면 스도쿠 보드를 출력하고 프로그램을 종료합니다.
마무리하며
이번 문제는 백트래킹을 사용해 스도쿠 퍼즐을 완성하는 과정에서 가능한 모든 경우를 탐색하며 해를 찾는 방법으로 문제를 해결하였습니다.