글 읽기 - 맞추긴 했지만 어떻게 하면 더 최적화 할 수 있는지 궁금합니다.

junah 2년 전 0

//2580  스도쿠

#include <stdio.h>

int map[10][10];
int ten[10];
int is_print = 0;

void print_map() {
    for(int i=1;i<=9;i++) {
        for(int j=1;j<=9;j++) {
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
}

int get_pos(int pos) {
    if(pos<=3) return 1;
    else if(pos<=6) return 4;
    return 7;
}

void check(int x,int y) {
    //초기화
    for(int i=1;i<=9;i++) ten[i]=1;
    //x 체크
    for(int i=1;i<=9;i++) {
        ten[map[y][i]] = 0;
    }
    //y 체크
    for(int i=1;i<=9;i++) {
        ten[map[i][x]] = 0;
    }
    //3x3 체크
    for(int i=get_pos(y);i<get_pos(y)+3;i++) {
        for(int j=get_pos(x);j<get_pos(x)+3;j++) {
            ten[map[i][j]] = 0;
        }
    }
}

void f(int x,int y) {
    //출력되었을때
    if(is_print) return;
    //종료 조건
    else if(x==1&&y==10) {
        print_map();
        is_print=1;
        return;
    }
    //해당 값이 0이 아닐때
    else if(map[y][x]!=0) {
        if(x==9) f(1,y+1);
        else f(x+1,y);
        return;
    }
    //해당 값이 0일때
    else {
        for(int i=1;i<=9;i++) {
            check(x,y);
            if(ten[i]) {
                map[y][x]=i;
                if(x==9) f(1,y+1);
                else f(x+1,y);
                map[y][x]=0;
            }
        }
    }
    return;
}

int main() {
    for(int i=1;i<=9;i++) {
        for(int j=1;j<=9;j++) {
            scanf("%d",&map[i][j]);
        }
    }
    f(1,1);
    return 0;
}

wider93 2년 전 0

코드에 크게 비효율적인 부분은 없습니다. 더 최적화하려면 비트마스킹을 한다거나 등의 로우레벨 설계를 바꾸는 작업이 주가 될 텐데, 작은 부분들이 쌓여서 커지는 식이라 하나하나 여기를 바꾸라고 짚어주기는 어렵습니다. 다른 분들의 빠른 코드를 읽어보면서 참고하는 게 더 좋은 방법이 될 겁니다.

junah 2년 전 0

다른 코드를 아예 참고 안하고 직접 짠 코드여서 많이 비효율적이라고 생각했는데,

크게 비효율적인 부분은 없다고 하시니 다행이네요.

답변 감사합니다.

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

문제

문제

출처

ICPC

맞추긴 했지만 어떻게 하면 더 최적화 할 수 있는지 궁금합니다.

junah 2년 전 0

wider93 2년 전 0

junah 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말