글 읽기 - 어디가 문제인지 잘 모르겠습니다.

th11181 4년 전 0

예제는 돌아가는데
0 0 3 4 5 6 7 8 9
4 5 6 7 8 9 0 0 3
7 8 9 0 0 3 4 5 6
0 0 4 3 6 5 8 9 7
3 6 5 8 9 7 0 0 4
8 9 7 0 0 4 3 6 5
5 3 0 6 4 0 9 7 8
6 4 0 9 7 8 5 3 0
9 7 8 5 3 0 6 4 0
이걸로 하면
그대로 다시
0 0 3 4 5 6 7 8 9
4 5 6 7 8 9 0 0 3
7 8 9 0 0 3 4 5 6
0 0 4 3 6 5 8 9 7
3 6 5 8 9 7 0 0 4
8 9 7 0 0 4 3 6 5
5 3 0 6 4 0 9 7 8
6 4 0 9 7 8 5 3 0
9 7 8 5 3 0 6 4 0
출력됩니다
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int sdo[][] = new int[9][9];
	static int sdo2[][] = new int[9][9];
	static int[] arr;
	static int length = 0;
	static boolean[][] chk;
	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = 0;
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				sdo[i][j] = sc.nextInt();
				sdo2[i][j] = sdo[i][j];
				if(sdo[i][j] == 0) {
					num++;
				}
			}
		}
		
		length = num;
		arr = new int[num];
		chk = new boolean[num][10];
		
		int ad = 0;
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				if(sdo[i][j] == 0) {
					for(int k=0; k<9; k++) {
						chk[ad][sdo[i][k]] = true;
						chk[ad][sdo[k][j]] = true;
					}
					if(i/3 == 0 && j/3 == 0) {
						for(int k=0; k<3; k++) {
							for(int g=0; g<3; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 0 && j/3 == 1) {
						for(int k=0; k<3; k++) {
							for(int g=3; g<6; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 0 && j/3 == 2) {
						for(int k=0; k<3; k++) {
							for(int g=6; g<9; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 1 && j/3 == 0) {
						for(int k=3; k<6; k++) {
							for(int g=0; g<3; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 1 && j/3 == 1) {
						for(int k=3; k<6; k++) {
							for(int g=3; g<6; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 1 && j/3 == 2) {
						for(int k=3; k<6; k++) {
							for(int g=6; g<9; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 2 && j/3 == 0) {
						for(int k=6; k<9; k++) {
							for(int g=0; g<3; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 2 && j/3 == 1) {
						for(int k=6; k<9; k++) {
							for(int g=3; g<6; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}else if(i/3 == 2 && j/3 == 2) {
						for(int k=6; k<9; k++) {
							for(int g=6; g<9; g++) {
								chk[ad][sdo[k][g]] = true;
							}
						}
					}
					ad++;
				}
			}
		}
		
		backt(0);
		
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				System.out.print(sdo[i][j]);
			}
			System.out.println();
		}
	}
	
	static boolean backt(int a) {
		if(a == length) {
			int num = 0;
			for(int i=0; i<9; i++) {
				for(int j=0; j<9; j++) {
					if(sdo[i][j] == 0) {
						sdo[i][j] = arr[num];
						num++;
					}
				}
			}
			
			if(isPossible() == true) {
				return true;
			}else {
				for(int i=0; i<9; i++) {
					for(int j=0; j<9; j++) {
						sdo[i][j] = sdo2[i][j];
					}
				}
				return false;
			}
			
		}
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				if(sdo[i][j] == 0) {
					if(chk[a][j+1] == false) {
						chk[a][j+1] = true;
						arr[a] = j+1;
						if(backt(a+1) == true) {
							return true;
						}
					}
				}
			}
		}
		return false;
	}
	
	static boolean isPossible() {
		boolean chk2[] = new boolean[10];
		for(int i=0; i<10; i++) {
			chk2[i] = false;
		}
		int cnt = 0;
		//가로
		for(int i=0; i<9; i++) {
			if(i==0) {
				cnt++;
			}
			
			for(int j=0; j<9; j++) {
				if(chk2[sdo[j][i]] == true) {
					return false;
				}
				chk2[sdo[j][i]] = true;
			}
			for(int k=1; k<10; k++) {
				chk2[k] = false;
			}
			
		}
		//세로
		for(int i=0; i<9; i++) {
			if(i==0) {
				cnt++;
			}
			for(int j=0; j<9; j++) {
				if(chk2[sdo[i][j]] == true) {
					return false;
				}
				chk2[sdo[i][j]] = true;
			}
			for(int k=1; k<10; k++) {
				chk2[k] = false;
			}			
		}
		//구역
		for(int i=0; i<9; i++) {
			if(i==0) {
				cnt++;
			}
			for(int j=0; j<9; j++) {
				if(i/3 == 0 && j/3 == 0) {
					for(int k=0; k<3; k++) {
						for(int g=0; g<3; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 0 && j/3 == 1) {
					for(int k=0; k<3; k++) {
						for(int g=3; g<6; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 0 && j/3 == 2) {
					for(int k=0; k<3; k++) {
						for(int g=6; g<9; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 1 && j/3 == 0) {
					for(int k=3; k<6; k++) {
						for(int g=0; g<3; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 1 && j/3 == 1) {
					for(int k=3; k<6; k++) {
						for(int g=3; g<6; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 1 && j/3 == 2) {
					for(int k=3; k<6; k++) {
						for(int g=6; g<9; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 2 && j/3 == 0) {
					for(int k=6; k<9; k++) {
						for(int g=0; g<3; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 2 && j/3 == 1) {
					for(int k=6; k<9; k++) {
						for(int g=3; g<6; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}else if(i/3 == 2 && j/3 == 2) {
					for(int k=6; k<9; k++) {
						for(int g=6; g<9; g++) {
							if(chk2[sdo[k][g]] == true) {
								return false;
							}
							chk2[sdo[k][g]] = true;
						}
						for(int l=1; l<10; l++) {
							chk2[l] = false;
						}	
					}
				}
			}
		}
		
		if(cnt == 3) {
			return true;
		}
		return false;
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

어디가 문제인지 잘 모르겠습니다.

th11181 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
