글 읽기 - C++ 스포주의)더 빠른시간내에 풀수있는 방법이 있을까요?

gmlrhks95 3년 전 0

시간 대략 200ms 나오는 코드 입니다.

통과는 해서 다른분들과 제 로직을 비교해봣는데 어느 부분에서 속도가 떨어지는건지 감이 안잡히네요

개선할 부분 있으면 지적해주시면 감사하겠습니다.

DFS & 백트래킹 기법을 사용했습니다.

#include <stdio.h>

#define idx_to_sq(a, b) a / 3 * 3 + b / 3
using namespace std;
int row[9][10], col[9][10], sq[9][10];
int sdoku[9][9];

bool DFS(int x, int y) {
    if (y == 9)
        return true;

    while (sdoku[x][y]) {
        x = x + 1;
        if (x == 9) {
            x = 0;
            y = y + 1;
        }
        if (y == 9)
            return true;
    }

    int nx = x + 1;
    int ny = y;

    if (nx == 9) {
        nx = 0;
        ny = y + 1;
    }

    for (int i = 1; i <= 9; i++) {
        if (row[x][i] && col[y][i] && sq[idx_to_sq(x, y)][i]) {
            sdoku[x][y] = i;
            row[x][i] = col[y][i] = sq[idx_to_sq(x, y)][i] = false;

            if (DFS(nx, ny))
                return true;

            sdoku[x][y] = 0;
            row[x][i] = col[y][i] = sq[idx_to_sq(x, y)][i] = true;
        }
    }
    return false;
}

int main() {
    for (size_t i = 0; i < 9; i++) {
        for (size_t j = 0; j < 10; j++) {
            row[i][j] = true;
            col[i][j] = true;
            sq[i][j] = true;
        }
    }

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%d", &sdoku[i][j]);
            if (sdoku[i][j]) {
                row[i][sdoku[i][j]] = false;
                col[j][sdoku[i][j]] = false;
                sq[idx_to_sq(i, j)][sdoku[i][j]] = false;
            }
        }
    }

    DFS(0, 0);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            printf("%d ", sdoku[i][j]);
        printf("\n");
    }

    return 0;
}

sohnryang 3년 전 0

이 글을 읽어보시면 도움이 될 것 같네요.

https://norvig.com/sudoku.html

위 글에 설명되어 있는거 말고도 DLX 알고리즘을 사용할 수도 있는걸로 알고 있습니다.

moon960323 3년 전 0

while문으로 빈칸을 찾는 것보다는 처음부터 빈칸의 정보를 저장해둔 뒤에 하나씩 꺼내쓰게 하면

조금 더 최적화 시킬 수 있을 것 같네요

// 해당 부분
while (sdoku[x][y]) {
        x = x + 1;
        if (x == 9) {
            x = 0;
            y = y + 1;
        }
        if (y == 9)
            return true;
    }

// 예시
bool DFS(int index)
{
    int x = blank_x[index];
    int y = blank_y[index];
    
    ...
        
    DFS(index+1)
        
    ...
    
}

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

문제

문제

출처

ICPC

C++ 스포주의)더 빠른시간내에 풀수있는 방법이 있을까요?

gmlrhks95 3년 전 0

sohnryang 3년 전 0

moon960323 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말