4056번: 스-스-스도쿠
바다에서 수학을 좋아하기로 유명한 오징어의 취미는 스도쿠이다. 스도쿠는 9*9칸으로 이루어져 있으며, 3*3칸에 1~9까지가 1번씩, 각각의 가로줄에도 1번씩, 세로줄에도 1번씩 들어가게 만드는 게
www.acmicpc.net
0. 기존 스도쿠 코드의 활용(링크)
1. 기존 코드부터 true/false 리턴값으로 성공/실패를 알 수 있으니 함수 내부는 추가적 처리 불필요
2. 초기 입력값부터 규칙에 위배될 수 있으니, 시작하기 전 체크한다
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main{
static int[][] map;
static boolean[][]rowChk;
static boolean[][]colChk;
public static void main(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int tc = pint(br.readLine());
for (int testcase = 1; testcase <= tc; testcase++) {
int N = 9;
map = new int[N][N];
boolean success=true;
rowChk = new boolean[N][N+1];
colChk = new boolean[N][N+1];
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j]=s.charAt(j)-'0';
if(map[i][j]!=0) {
if(!rowChk[i][map[i][j]])rowChk[i][map[i][j]]=true;
else success=false;//row체크
if(!colChk[j][map[i][j]])colChk[j][map[i][j]]=true;
else success=false;//col체크
}
}
}
//block 체크
for (int bx = 0; bx < 9; bx+=3) {
for (int by = 0; by < 9; by+=3) {
boolean[]blockChk=new boolean[N+1];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(map[bx+i][by+j]==0)continue; // 0일때는 넘어간다
if(!blockChk[ map[bx+i][by+j] ])
blockChk[ map[bx+i][by+j] ]=true;//0이 아닌 값을 처음 만나면 true
else {
success=false;//0이 아닌 값을 다시 만나면 실패한 스도쿠
}
}
}
}
}
//초기 입력값이 valid하다면
if(success)success = rec(0);
if(success) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(map[i][j]);
}sb.append('\n');
}
}
else {
sb.append("Could not complete this grid.\n");
}sb.append('\n');
}System.out.println(sb);
}
static boolean rec(int cur) {
if(cur==81)return true;
int x = cur/9;
int y = cur%9;
if(map[x][y]==0) {
for (int i = 1; i <= 9; i++) {
if(chk(x,y,(x/3)*3, (y/3)*3, i)) {
rowChk[x][i]=true;
colChk[y][i]=true;
map[x][y]=i;
if(rec(cur+1))return true;
rowChk[x][i]=false;
colChk[y][i]=false;
}
}
map[x][y]=0;
}
else {
//이미 뭔가 수가 있다
return rec(cur+1);
}
return false;
}
static boolean chk(int row, int col, int x, int y, int val) {
boolean ret=true;
if(rowChk[row][val] || colChk[col][val])ret=false;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if(map[x+i][y+j]==val)ret=false;
return ret;
}
static int pint(String s) {
return Integer.parseInt(s);
}
}
'알고리즘 문제 풀이 > BOJ 골드' 카테고리의 다른 글
| [백준] 1967 - 트리의 지름 (0) | 2021.04.18 |
|---|---|
| [백준] 2263 - 트리의 순회 (0) | 2021.04.16 |
| [백준] 17471 - 게리맨더링 (0) | 2021.04.16 |
| [백준] 2239 - 스도쿠 (0) | 2021.04.16 |
| [백준] 2096 - 내려가기 (0) | 2021.04.16 |
| [백준] 15961 - 회전 초밥 (0) | 2021.04.15 |
| [백준] 2638 - 치즈 (0) | 2021.04.15 |
