글 읽기 - [JAVA] 반례를 찾지 못하겠습니다.

eungu0920 4년 전 0

이제 막 알고리즘을 입문하여 문제를 풀고있습니다.

먼저 코드길이도 길고 난잡하여 보기 힘드실텐데 봐주셔서 감사합니다.

단계별로 풀어보기 백트래킹 단계의 앞단계 문제들은 다 풀고 이제 스도쿠 문제를 풀고있습니다.

아직 백트래킹에 대한 개념이 잡히지 못하여 난잡하게 코딩을 하였는데 틀렸습니다가 나오네요...

Backtracking함수의 첫 번째 for문은 스도쿠의 빈칸에 1~9까지 맞는 숫자를 입력하는 문이며

그 다음 차례로 나오는 for문들은 행, 열, 박스(9가지경우)검사입니다.

예제는 맞게 나오는데 어떤케이스에서 틀렸습니다가 나오는지 찾지못하겠습니다.

도와주시면 감사하겠습니다..!

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[][] Sudoku = new int[10][10];
	static int[] Blank = new int[81];
	static boolean[] width = new boolean[10];
	static boolean[] height = new boolean[10];
	static boolean[] box = new boolean[10];
	static int X, Y;
	static boolean Result;
	
	static void Backtracking(int start, int count) {
		if(count == 0) {
			for(int i = 1; i < 10; i++) {
				for(int j = 1; j < 10; j++) {
					System.out.print(Sudoku[i][j]);
					if(j != 9)
						System.out.print(" ");
				}
				if(i != 9)
					System.out.println();
			}
			return;
		}
		
		X = Blank[start] / 10;
		Y = Blank[start] - X*10;
		
		for(int i = 1; i < 10; i++) {
			Arrays.fill(box, false);
			Arrays.fill(width, false);
			Arrays.fill(height, false);
			Result = false;
			
			Sudoku[X][Y] = i;
			
			width[i] = height[i] = box[i] = true;
			
			for(int j = 1; j < 10; j++) {
				if(j == Y || Sudoku[X][j] == 0)
					continue;
				if(width[Sudoku[X][j]] == false)
					width[Sudoku[X][j]] = true;
				else
					Result = true;
			}
			
			for(int j = 1; j < 10; j++) {
				if(j == X || Sudoku[j][Y] == 0)
					continue;
				if(height[Sudoku[j][Y]] == false)
					height[Sudoku[j][Y]] = true;
				else
					Result = true;
			}
			
			if(X % 3 == 1 && Y % 3 == 1) {
				for(int j = X; j < X+3; j++) {
					for(int k = Y; k < Y+3; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 1 && Y % 3 == 2) {
				for(int j = X; j < X+3; j++) {
					for(int k = Y-1; k < Y+2; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 1 && Y % 3 == 0) {
				for(int j = X; j < X+3; j++) {
					for(int k = Y-2; k < Y+1; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 2 && Y % 3 == 1) {
				for(int j = X-1; j < X+2; j++) {
					for(int k = Y; k < Y+3; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 2 && Y % 3 == 2) {
				for(int j = X-1; j < X+2; j++) {
					for(int k = Y-1; k < Y+2; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 2 && Y % 3 == 0) {
				for(int j = X-1; j < X+2; j++) {
					for(int k = Y-2; k < Y+1; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 0 && Y % 3 == 1) {
				for(int j = X-2; j < X+1; j++) {
					for(int k = Y; k < Y+3; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 0 && Y % 3 == 2) {
				for(int j = X-2; j < X+1; j++) {
					for(int k = Y-1; k < Y+2; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(X % 3 == 0 && Y % 3 == 0) {
				for(int j = X-2; j < X+1; j++) {
					for(int k = Y-2; k < Y+1; k++) {
						if((j == X && k == Y) || Sudoku[j][k] == 0)
							continue;
						if(box[Sudoku[j][k]] == false)
							box[Sudoku[j][k]] = true;
						else
							Result = true;
					}
				}
			}
			
			if(!Result)
				Backtracking(++start, --count);
			
		}
		
		
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = 0;
		
		for(int i = 1; i < 10; i++) {
			String[] Input = sc.nextLine().split(" ");
			for(int j = 1; j < 10; j++) {
				Sudoku[i][j] = Integer.parseInt(Input[j-1]);
				if(Integer.parseInt(Input[j-1]) == 0) {
					Blank[count++] = i * 10 + j;
				}
			}
		}

		Backtracking(0, count);	
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[JAVA] 반례를 찾지 못하겠습니다.

eungu0920 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말