글 읽기 - 시간 초과 반례가 궁금합니다. 도와주세요 존경하는 고수님들....

ebseud6135 4년 전 1

한번 삽입 할때마다 check메소드로 검사하기 때문에

시간초과인 것도 알겠고 다른 효율적인 구현방법들이 있다는 것도 알고있습니다..

하지만 저의 의문점은

0 0 0 0 0 0 0 0 0

이 예제가 1초안에 통과를 하는데

왜 시간초과가 나오는지 모르겠습니다.

위의 예제보다 더 시간이 오래걸리는 반례가 있나요?

게시판의 코드들도 대부분? 1초안에 통과했습니다..

다른 반례가 있다면 이유도 좀 부탁합니다.. 고수님들 ㅠㅠㅠㅠ

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

public class Main {
	public static boolean check(int[][]a) {
		boolean[]b = new boolean[9];
		for(int i=0; i<3; i++) {
			for(int j=0; j<9; j++) {
				Arrays.fill(b, false);
				for(int k=0; k<9; k++) {
					int v = 0;
					if(i==0) { //행 검사
						v = a[j][k];
					}else if(i==1) { //열 검사
						v = a[k][j]; 
					}else {
						v = a[j/3*3+k/3][j%3*3+k%3];
					}
					if(v==0) continue;
					if(b[v-1]) return false;
					b[v-1] = true;
				}
			}
		}
		return true;
	}

	public static void go(int[][]a, int cnt) {
		if(cnt == 81) {
			for(int i=0; i<9; i++) {
				for(int j=0; j<9; j++) {
					System.out.print(a[i][j]+" ");
				}
				System.out.println();
			}
			System.exit(0);
		}
		int row = cnt/9;
		int col = cnt%9;
		int v = a[row][col];
		if(v != 0) { 
			go(a, cnt+1);
		}else {
			for(int i=1; i<=9; i++) {
				a[row][col] = i;
				if(check(a)) {
					go(a, cnt+1);
				}
			}
			a[row][col] = 0;
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[][]a = new int[9][9];
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				a[i][j] = scan.nextInt();
			}
		}
		go(a,0);
		for(int i=0; i<9; i++) {
			for(int j=0; j<9; j++) {
				System.out.print(a[i][j]+" ");
			}
			System.out.println();
		}
	}
}

djm03178 4년 전 8

0으로 가득 채워진 판은 매우 금방 답 하나를 찾아낼 수 있기 때문에 빠릅니다.

https://en.wikipedia.org/wiki/Sudoku_solving_algorithms 에 있는, 일반적인 브루트 포스를 가장 오래 걸리게 하는 예시를 넣으면 아주 아주 오랜 시간이 걸리는 것을 볼 수 있습니다.

물론 이 예시는 정말로 브루트 포스가 최악이 되도록 만든 것이고, 이 문제에서 이렇게 강력한 예시는 암묵적으로 쓰지 않고 있지만 (이 케이스를 넣었다간 거의 대부분의 정답 코드들이 날아갈 것입니다), 이에 준하는 정도의 케이스는 얼마든지 있을 수 있습니다.

0 0 0 0 0 0 0 0
0 0 0 0 3 0 8 5
0 1 0 2 0 0 0 0
0 0 5 0 7 0 0 0
0 4 0 0 0 1 0 0
9 0 0 0 0 0 0 0
0 0 0 0 0 0 7 3
0 2 0 1 0 0 0 0
0 0 0 4 0 0 0 9

ebseud6135 4년 전 0

전부 0인 경우가 가장 느린 것이 아니였군요..

저의 얕은 지식에 한숨이 나오는군여..

고수님 감사합니다 ~~~~~b

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

문제

문제

출처

ICPC

시간 초과 반례가 궁금합니다. 도와주세요 존경하는 고수님들....

ebseud6135 4년 전 1

djm03178 4년 전 8

ebseud6135 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말