[백준] 알고리즘 분류(구현,JAVA)2239번, 스도쿠

문제 링크

2239번: 스도쿠

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 스도쿠의 룰에 맞게 보드를 채워야합니다.

스도쿠 - 위키백과, 우리 모두의 백과사전

2. 답이 여러개 있으면 81자리의 수가 제일 작은 경우를 출력합니다.

3. 보드를 모두 채운 후 보드의 값들을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 보드에 값 채우기를 진행합니다.

 

3. 가장 먼저 채워진 보드의 값들을 결과로 출력합니다.

 

 

보드 값 채우기

 

스도쿠는 기본적으로

 

열, 행, 3 × 3칸에서 1~9 중복되지 않는 값을 가져야합니다.

 

저는 중복되는 값이 들어가지 않도록 3차원 boolean형 배열을 만들어서 사용하였습니다.

 

boolean[i][j][k]

 

i : 행, 열, 3 × 3 구분

j : j번째 행, 열, 3 × 3

 

k : 수

 

booelan[0][2][3] = true

 

해석 : 2번째 행에서 숫자 3은 사용되었습니다.

 

boolean[2][3][9] = true

 

해석 : 3번째 3 × 3 칸에서 숫자 9는 사용되었습니다.

 

이를 이용해서 중복되지 않는 값을 보드에 저장되지 않도록 백트래킹을 하였습니다.

 

답이 여러 개일 때 사전순으로 빠른 것을 찾기 위해서

 

보드에 들어가는 값들을 탐색할 때 1부터 탐색을 진행하여 넣을 수 있는 숫자를 탐색하였습니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

스도쿠 보드 정보

 

1	0	3	0	0	0	5	0	9
0	0	2	1	0	9	4	0	0
0	0	0	7	0	4	0	0	0
3	0	0	5	0	2	0	0	6
0	6	0	0	0	0	0	5	0
7	0	0	8	0	3	0	0	4
0	0	0	4	0	1	0	0	0
0	0	9	2	0	5	8	0	0
8	0	4	0	0	0	1	0	7

 

2. 보드에 값 채우기를 진행합니다.

 

보드 값 채우기!

(1, 1)

 

1	4	3	0	0	0	5	0	9
0	0	2	1	0	9	4	0	0
0	0	0	7	0	4	0	0	0
3	0	0	5	0	2	0	0	6
0	6	0	0	0	0	0	5	0
7	0	0	8	0	3	0	0	4
0	0	0	4	0	1	0	0	0
0	0	9	2	0	5	8	0	0
8	0	4	0	0	0	1	0	7

 

1 : boolean[0][0][1] = true

2 : boolean[2][0][2] = true

3 : boolean[0][0][3] = true

4 : X

4는 행, 열, 3 × 3에 사용되지 않아서 4를 넣어보고 탐색을 계속 진행합니다.

 

(0, 3)

 

1	4	3	6	0	0	5	0	9
0	0	2	1	0	9	4	0	0
0	0	0	7	0	4	0	0	0
3	0	0	5	0	2	0	0	6
0	6	0	0	0	0	0	5	0
7	0	0	8	0	3	0	0	4
0	0	0	4	0	1	0	0	0
0	0	9	2	0	5	8	0	0
8	0	4	0	0	0	1	0	7

 

1 : boolean[0][0][1] = true

2 : boolean[1][3][2] = true

3 : boolean[0][0][3] = true

4 : boolean[0][0][4] = true

5 : boolean[0][0][5] = true

6 : X

6는 행, 열, 3 × 3에 사용되지 않아서 6를 넣어보고 탐색을 계속 진행합니다.

 

....

 

1	4	3	6	2	8	5	7	9
5	7	2	1	3	9	4	6	8
9	8	6	7	5	4	2	3	1
3	9	1	5	4	2	7	8	6
4	6	8	9	1	7	3	5	2
7	2	5	8	6	3	9	1	4
2	3	7	4	8	1	6	9	5
6	1	9	2	7	5	8	4	3
8	5	4	3	9	6	1	2	7

 

3. 가장 먼저 채워진 보드의 값들을 결과로 출력합니다.

 

1	4	3	6	2	8	5	7	9
5	7	2	1	3	9	4	6	8
9	8	6	7	5	4	2	3	1
3	9	1	5	4	2	7	8	6
4	6	8	9	1	7	3	5	2
7	2	5	8	6	3	9	1	4
2	3	7	4	8	1	6	9	5
6	1	9	2	7	5	8	4	3
8	5	4	3	9	6	1	2	7

 

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 

결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 스도쿠 보드의 값들 저장할 때 행, 열, 3 × 3칸에 사용되는 used[][][]배열에 반영합니다.
• sudokuSearch함수를 실행하여 보드의 값들을 채웁니다.
• 모두 채운 보드의 값을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• sudokuSearch함수는 백트래킹을 이용하여 보드의 값들을 채우기를 진행합니다.

 

결과코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int[][] sudoku = new int[9][9];	//스도쿠 보드 저장 배열
    //행, 열, 3 × 3칸 숫자 사용 여부 배열
    static boolean[][][] used = new boolean[3][9][10];
    static boolean end = false;	//탐색 종료 확인 변수
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //스도쿠 보드 정보 저장
        for(int i=0;i<9;i++) {
            String str = br.readLine();
            for(int j=0;j<9;j++) {
                sudoku[i][j] = Character.getNumericValue(str.charAt(j));
                if(sudoku[i][j] != 0) {
                    used[0][i][sudoku[i][j]] = true;	//행 숫자 사용
                    used[1][j][sudoku[i][j]] = true;	//열 숫자 사용
                    used[2][(i/3)*3 + j/3][sudoku[i][j]] = true;	//3 × 3칸 숫자 사용
                }
            }
        }
        //스도쿠 채우기
        sudokuSearch(0, 0);
        //스도쿠 정보 BufferedWriter 저장
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++)
                bw.write(sudoku[i][j] + "");
            bw.newLine();
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //스도쿠 보드 채우는 함수
    static void sudokuSearch(int x, int y) {
        //스도쿠 보드 마지막 칸일 때
        if(x == 8 && y == 8) {
            for(int i=1;i<=9;i++) {
                if(!used[0][8][i]) {
                    sudoku[8][8] = i;
                    break;
                }
            }
            end = true;		//보드 완성!
            return;
        }
        //Default로 숫자가 존재하는 칸일 때
        if(sudoku[y][x] != 0) {
            if(x + 1 == 9)	//다음 행으로 이동
                sudokuSearch(0, y+1);
            else	//다음 열으로 이동
                sudokuSearch(x+1, y);
        }else {
            //빈 칸일 때 1부터 순차적 백트래킹 탐색 진행!
            for(int i=1;i<=9;i++) {
                //사용하지 않은 숫자일 때
                if(!used[0][y][i] && !used[1][x][i] && !used[2][(y/3)*3 + x/3][i]) {
                    //숫자 사용
                    used[0][y][i] = true;
                    used[1][x][i] = true;
                    used[2][(y/3)*3+x/3][i] = true;
                    sudoku[y][x] = i;
                    if(x + 1 == 9)	//다음 행으로 이동
                        sudokuSearch(0, y+1);
                    else		//다음 열으로 이동
                        sudokuSearch(x+1, y);
                    if(end)
                        return;
                    //숫자 미사용
                    sudoku[y][x] = 0;
                    used[0][y][i] = false;
                    used[1][x][i] = false;
                    used[2][(y/3)*3 + x/3][i] =false;
                }
            }
        }
    }
}