[Gold IV] 스도쿠 - 2580
성능 요약
메모리: 27120 KB, 시간: 484 ms
분류
백트래킹
제출 일자
2024년 7월 3일 21:22:28
문제 설명
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
풀이 (백트래킹)
각각의 상황을 모두 구현해주면 된다.
- 세로로 해당 숫자가 가능한 지 확인하기
- 가로로 해당 숫자가 가능한 지 확인하기
- 3X3 박스로 해당 숫자가 가능한 지 확인하기
- 세로로 해당 숫자가 가능한 지 확인하기
public static boolean check_col(int col,int val) { //세로 행 조사
for(int i=0; i<9; i++) {
if(map[i][col]==val) { //해당 행에 같은 수가 있으면 안된다.
return false;
}
}
return true;
}- 가로로 해당 숫자가 가능한 지 확인하기
public static boolean check_row(int row,int val) { //가로 열 조사
for(int i=0; i<9; i++) {
if(map[row][i]==val) {//해당 열에 같은 수가 있으면 안된다.
return false;
}
}
return true;
}- 3X3 박스로 해당 숫자가 가능한 지 확인하기
public static boolean check_box(int row,int col,int val) { //해당 부분 3x3 박스 조사
int start_x = (row/3)*3; //시작 박스 조정
int start_y = (col/3)*3;
for(int i=start_x; i<start_x+3; i++) {
for(int j=start_y; j<start_y+3; j++) {
if(map[i][j]==val) { //3x3 박스내 같은 수가 있으면 안된다.
return false;
}
}
}
return true;
}그리고, 출력 부분을 확인해보면...
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
라고 나오는데 이 부분을 System.exit(0) 을 통해 실행해야 한다.
이 부분을 주의해주면서 백트래킹하면 된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
//백트래킹 문제
static int[][] map= new int[9][9];//9x9 스도쿠 배열
static StringBuilder sb = new StringBuilder(); //출력용
public static void main(String[] args) throws IOException {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
for(int i=0; i<9; i++) { //입력받기
st = new StringTokenizer(br.readLine());
for(int j=0; j<9; j++) {
map[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) { //행까지 채워지면 출력하기
for(int i=0; i<9; i++) {
for(int j=0; j<9; j++) {
sb.append(map[i][j]+" ");
}
sb.append("\n");
}
System.out.println(sb.toString());
System.exit(0); //하나의 답만 취급하므로 출력 후 종료하기.
}
if(map[row][col]==0) { //채워야 할 부분일 경우
for(int i=1; i<=9; i++) {
//가로 세로 3x3 박스 모두 가능한 숫자라면
if(check_row(row,i)==true && check_col(col,i)==true && check_box(row,col,i)==true) {
map[row][col]=i;
sudoku(row,col+1);
}
}
map[row][col]=0;
return;
}
sudoku(row,col+1);
}
public static boolean check_row(int row,int val) { //가로 열 조사
for(int i=0; i<9; i++) {
if(map[row][i]==val) {//해당 열에 같은 수가 있으면 안된다.
return false;
}
}
return true;
}
public static boolean check_col(int col,int val) { //세로 행 조사
for(int i=0; i<9; i++) {
if(map[i][col]==val) { //해당 행에 같은 수가 있으면 안된다.
return false;
}
}
return true;
}
public static boolean check_box(int row,int col,int val) { //해당 부분 3x3 박스 조사
int start_x = (row/3)*3; //시작 박스 조정
int start_y = (col/3)*3;
for(int i=start_x; i<start_x+3; i++) {
for(int j=start_y; j<start_y+3; j++) {
if(map[i][j]==val) { //3x3 박스내 같은 수가 있으면 안된다.
return false;
}
}
}
return true;
}
}[스도쿠 - 자바] 해당 블로그를 참고했다.
이 블로그를 참고하면서, 다시 생각해보면 굳이 메소드를 나눌 필요 없이 하나에다가 넣었어도 될 거 같다...
