글 읽기 - 맞긴했는데 밑의 urd05님의 글에 있는 데이터에 대해 질문입니다.

ckddn1224 3년 전 0

일단 제 소스는 이렇습니다.정답 받았습니다

그런데 밑의 urd05님의 데이터의 답을 5분넘게 돌려도 찾지못합니다.

정확히는 제 소스가 틀린건지 시간이 너무 오래걸리는 것인지 모르겠습니다.

제 소스를 고친다면 어디 부분을 고쳐야할까요 ?

복사붙여넣기할때 들어가서 지운다고 지웠는데

소스에 <i> </i>가 들어있는건 없다고 생각해주세요

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
    no.2580 : Sudoku
 */

public class BOJ2580 {
    static BufferedReader br;
    static BufferedWriter bw;
    static int[] arr = new int[81];     // sudoku input array
    static int[] arr_0 = new int[82];   // array of location 0
    static String s;

    static void sudoku(int i) throws IOException{
        int idx = arr_0[i];
//        System.out.println("idx = " + idx);
//        System.out.println("i = " + i);

        if (idx == -1){
            for(int a = 0; a < 81; a++){
                bw.write(arr[a] + " ");
                if ((a + 1) % 9 == 0)
                    bw.write("\n");
            }
            bw.flush();
            System.exit(0);
        } else {
            for (int k = 1; k < 10; k++){   // put num in until it can be possible
                arr[idx] = k;
//                System.out.println("k = " + k);

                if(isPossible(idx)){
                    sudoku(i + 1);
                }
                arr[idx] = 0;
            }
        }
    }
    static boolean isPossible(int idx){

        int row = idx / 9;
        int col = idx % 9;
        for (int k = 0; k < 9; k++){
            // check same col
            if (arr[9*k + col] != 0 && arr[idx] == arr[9*k + col] && idx != (9*k + col)){
//                System.out.println("collapse in col");
                return false;
            }
            // check same row
            if (arr[9*row + k] != 0 && arr[idx] == arr[9*row + k] && idx != (9*row + k)){
//                System.out.println("collapse in row");
                return false;
            }
        }
        // check 3x3 square
        int startI = (idx / 27) * 27 + ((idx % 9) / 3) * 3; // find block's first index
        for (int k = startI; k <= startI + 18; k += 9){
            for (int l = 0; l < 3; l++){
                if(arr[k+l] != 0 && arr[idx] == arr[k+l] && idx != k+l){
//                    System.out.println("collapse in 3x3");
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int idx = 0;
        int k = 0;
        int si = 0;

        Arrays.fill(arr_0, -1);

        for(int i = 0; i < 9; i++){
            s = br.readLine();
            StringTokenizer st = new StringTokenizer(s);
            for(int j = 0; j < 9; j++){
                si = Integer.parseInt(st.nextToken());
                arr[idx++] = si;
                if (si == 0)
                    arr_0[k++] = idx - 1;
            }
        }

        sudoku(0);

        br.close();
        bw.close();
    }
}

sait2000 3년 전 1

아마 그냥 느린 걸 겁니다. 이 문제는 데이터가 약한 편으로 알고 있습니다.

kyo20111 3년 전 1

예전에 논의된 적이 있었는데 교육용의 목적으로 백트래킹을 허용하는 쪽으로 결론났던 것 같습니다.

자세히 보질 않았어서 기억이 나지 않네요

ckddn1224 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

맞긴했는데 밑의 urd05님의 글에 있는 데이터에 대해 질문입니다.

ckddn1224 3년 전 0

sait2000 3년 전 1

kyo20111 3년 전 1

ckddn1224 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말