BOJ 2239
위 문제는 백준 사이트의 알고리즘 2239 문제에 관한 설명입니다.
문제
스도쿠는 매우 간단한 숫자 퍼즐이다.
9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에
1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다.
예를 들어 다음을 보자.
위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다.
각 행에 1부터 9까지의 숫자가 중복 없이 나오고,
각 열에 1부터 9까지의 숫자가 중복 없이 나오고,
각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에
1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.
입력
9개의 줄에 9개의 숫자로 보드가 입력된다.
아직 숫자가 채워지지 않은 칸에는 0이 주어진다.
출력
9개의 줄에 9개의 숫자로 답을 출력한다.
답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다.
즉, 81자리의 수가 제일 작은 경우를 출력한다.
package day1106;
import java.util.ArrayList;
import java.util.Scanner;
public class Main스도쿠 {
static boolean flag = false;
static char[][] map = new char[9][9];
static ArrayList<Point> arraylist = new ArrayList<Point>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for(int i = 0 ; i < 9; i++) {
String str = scanner.next();
for(int j = 0 ; j < 9; j++) {
map[i][j] = str.charAt(j);
if(map[i][j] =='0') arraylist.add(new Point(i,j));
}
}
dfs(0);
}
static void dfs(int index) {
if(index == arraylist.size()) {
for(int i = 0 ; i < 9; i++) {
for(int j = 0 ; j < 9; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
flag = true;
}
if(flag) {
return;
}
Point temp = arraylist.get(index);
boolean visit[] = new boolean[10];//가로
for(int y = 0; y < 9; y++) {
if(map[temp.x][y] !='0') visit[map[temp.x][y]-'0'] = true;
}
for(int x = 0; x < 9; x++) {
if(map[x][temp.y] !='0') visit[map[x][temp.y]-'0'] = true;
}
for(int x = (temp.x/3)*3; x < (temp.x/3)*3 + 3; x++) {
for(int y = (temp.y/3)*3; y < (temp.y/3)*3 + 3; y++) {
if(map[x][y]!='0') visit[map[x][y] -'0'] = true;
}
}
for(int i = 1; i <= 9; i++) {
if(!visit[i]) {
map[temp.x][temp.y] = (char)(i+'0');// 넣고
dfs(index + 1);
map[temp.x][temp.y] = '0';//안뽑고
}
}
}
static class Point{
int x;
int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
}
이번 문제는 재귀를 사용했습니다.
static boolean flag = false;
static char[][] map = new char[9][9];
static ArrayList<Point> arraylist = new ArrayList<Point>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
for(int i = 0 ; i < 9; i++) {
String str = scanner.next();
for(int j = 0 ; j < 9; j++) {
map[i][j] = str.charAt(j);
if(map[i][j] =='0') arraylist.add(new Point(i,j));
}
}
dfs(0);
}
static 변수 사용과, 입력부 입니다.
flag는 나중에 스도쿠 판이 완성 되었을때 탈출 조건으로 사용합니다.
map은 9x9사이즈로 만들어야하며,
arraylist는 스도쿠에서 비어있는 자리(0)를 기억하도록 사용합니다.
static void dfs(int index) {
if(index == arraylist.size()) {
for(int i = 0 ; i < 9; i++) {
for(int j = 0 ; j < 9; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
flag = true;
}
if(flag) {
return;
}
Point temp = arraylist.get(index);
boolean visit[] = new boolean[10];//가로
for(int y = 0; y < 9; y++) {
if(map[temp.x][y] !='0') visit[map[temp.x][y]-'0'] = true;
}
for(int x = 0; x < 9; x++) {
if(map[x][temp.y] !='0') visit[map[x][temp.y]-'0'] = true;
}
for(int x = (temp.x/3)*3; x < (temp.x/3)*3 + 3; x++) {
for(int y = (temp.y/3)*3; y < (temp.y/3)*3 + 3; y++) {
if(map[x][y]!='0') visit[map[x][y] -'0'] = true;
}
}
for(int i = 1; i <= 9; i++) {
if(!visit[i]) {
map[temp.x][temp.y] = (char)(i+'0');// 넣고
dfs(index + 1);
map[temp.x][temp.y] = '0';//안뽑고
}
}
}
재귀부 입니다.
크게 3가지로 나눠서 설명하겠습니다.
if(index == arraylist.size()) {
for(int i = 0 ; i < 9; i++) {
for(int j = 0 ; j < 9; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
flag = true;
}
if(flag) {
return;
}
기저부분입니다.
조건은 0으로 된 자리들을 전부 arraylist에 담아놓았기 때문에, 그 크기만큼 다 채워졌을 경우
종료합니다.
그리고 출력합니다.
출력을 마치고 나왔을때 flag를 true로 설정해 이후로도 return 되도록 해줬습니다.
처음에 flag = true 부분을 return으로 처리하려니 재귀에서 한번만 돌아가고,
다시 동작해서 실패가 나왔었습니다.
Point temp = arraylist.get(index);
boolean visit[] = new boolean[10];
for(int y = 0; y < 9; y++) {
if(map[temp.x][y] !='0') visit[map[temp.x][y]-'0'] = true;
}
for(int x = 0; x < 9; x++) {
if(map[x][temp.y] !='0') visit[map[x][temp.y]-'0'] = true;
}
for(int x = (temp.x/3)*3; x < (temp.x/3)*3 + 3; x++) {
for(int y = (temp.y/3)*3; y < (temp.y/3)*3 + 3; y++) {
if(map[x][y]!='0') visit[map[x][y] -'0'] = true;
}
}
사용했던 숫자들을 확인하는 부분입니다.
스도쿠는 가로, 세로, 그리고 본인이 포함된 3x3의 구역에서 숫자가 하나씩 사용되어야합니다.
맨위 반복문은 가로에 사용된 숫자들을 확인하고,
가운데 반복문은 세로에 사용된 숫자들을 확인하고,
맨 아래 반복문은 예를들어 temp.x와 temp.y가 4, 4라고했을때
해당 반복문은 4/3 = 1 -> 1 * 3으로 3, 3부터시작해서 5, 5 까지 반복문이 동작합니다.
for(int i = 1; i <= 9; i++) {
if(!visit[i]) {
map[temp.x][temp.y] = (char)(i+'0');// 넣고
dfs(index + 1);
map[temp.x][temp.y] = '0';//안뽑고
}
}
그리고 나서 1~9까지의 숫자를 넣으면서 확인을 하는데,
위에서 알아낸 숫자들이 사용유무를 보고, 사용한 적이 없다면
그 숫자를 해당칸에다가 넣어줍니다.
그리고 dfs를 다시 동작시키는데 만약 충족하지 못해서 돌아온다면 그 숫자를 다른수로 바꾸면서 진행합니다.