글 읽기 - [java] 왜 틀렸는지 모르겠습니다 ㅠㅜ

corya4 4년 전 0

예제 및 다른 예제와 모두 0으로 돌려봤는데 정상적으로 출력되었습니다만...

어떤 실수를 했는지 자꾸 틀렸다고 나오네요 ㅠㅠ 아마 더블배열에안에 0이 있는만큼 숫자를 담은 변수가 문제인거 같기는 한데..

부탁드립니다 ㅠ

import java.util.Scanner;
import java.util.stream.Stream;

public class Main {
	static int[][] table = new int[9][9];
	static int zeroCount = 1;
	public static void main(String[] args){
		int count = setting();
		backTracking(count);
	}// End main method

	static void backTracking(int count) {
		
		if(zeroCount == 0) {
			count--;
			if (count <= 0) {
				for (int[] a : table) {
					for (int b : a) {
						System.out.print(b + " ");
					}
					System.out.println();
				}
				System.exit(0);
			}
		}else {
			zeroCount--;
		}
		
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				
				if (table[i][j] == 0) {
					for (int z = 1; z <= 9; z++) {
						if (checkingNum(z, i, j)) {
							table[i][j] = z;
							
							backTracking(count);
						} else {
							if (z == 9) {
								table[i][j] = 0;
								return;
							}
						}
					}
				}//if
			
			}
		}
	backTracking(count);
	}

	static boolean checkingNum(int num, int i, int j) {
		for (int row = 0; row < table.length; row++) {
			if (table[i][row] == num) {
				return false;
			}
			if (table[row][j] == num) {
				return false;
			}
		}
		int ibegin = (i / 3) * 3;
		int iend = ibegin + 3;
		int jbegin = (j / 3) * 3;
		int jend = jbegin + 3;
		for (int row = ibegin; row < iend; row++) {
			for (int col = jbegin; col < jend; col++) {
				if (table[row][col] == num) {
					return false;
				}
			}
		}
		
		return true;
	}

	
	  static int setting() { 
		  Scanner sc = new Scanner(System.in); 
		  for(int i = 0; i< table.length; i++) {
			  table[i] =Stream.of(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	  int Count = 0; 
	  for(int[] a: table) {
		  for(int b: a) {
			  if(b==0) {
				  Count++;
			  }
			} 
		 }
	  sc.close();
	  return Count; 
	  }
}

djm03178 4년 전 1

현재 39번째 줄은 마지막에 9를 넣어볼 수 있었다면 실행되지 않지만, 백트래킹을 올바르게 하려면 9를 넣을 수 있었는지 여부와는 관계 없이 0으로 초기화를 시켜야 합니다. 그것만 고치면 맞습니다.

corya4 4년 전 0

감사합니다 바로 해결되었습니다! 백트래킹 문제가 이번이 처음이라 ㅎㅎ... 그 후에비록 시간초과가 떳지만 해결해보겠습니다!

djm03178 4년 전 0

이 코드에서 말씀드린 부분 하나만 딱 고쳤는데 592ms로 잘 통과됩니다. 시간 초과가 났다면 어딘가 다른 곳도 불필요하게 고치신 겁니다.

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

문제

문제

출처

ICPC

[java] 왜 틀렸는지 모르겠습니다 ㅠㅜ

corya4 4년 전 0

djm03178 4년 전 1

corya4 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말