글 읽기 - c언어 맞추긴 했는데 재귀함수 종료 조건을 잘 모르겠습니다

dltjr0703 2년 전 0

저는 문제를 이렇게 풀었어요(맞추긴 했습니다)

"빈칸이 채워지는 조건이 항상 맞다는 가정 하에 마지막 빈칸이 채워지면 스도쿠 풀이 끝"

이렇게 풀었는데

exit(0)를 하지 않으면, 즉 프로그램 강제 종료하지 않는 이상 마지막 빈칸이 채워져도

다시 스택에 있는 걸 꺼내서 또 다시 다음 숫자를 대입하더라구요

예를 들어 0 0 0 ... 0 0 0을 넣어다 치면

dfs(81,81)에서 종료해야하는데(81번째 빈칸, 즉 마지막 빈칸을 채움)

dfs(81,81)전에 스택에 있던 dfs(80,80)의 그 다음 코드를 실행, 그 전 스택 다음 코드 실행....이렇게되서 실행을 너무 많이 하더라구요

이럴 땐 무슨 재귀 함수 종료 조건을 써야할까요?

(함수가 정상 종료되었으면 좋겠습니다)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

int blank_cnt;
int sudoku[9][9];
bool n[80][10] ={false,};

struct coordinate{
    int x; int y;
};

struct coordinate blank[81];


int section(int a){
    switch (a)
    {
        case 2:
        case 1:
        case 0: return 0;
        case 5:
        case 4:
        case 3: return 3;
        case 8:
        case 7:
        case 6: return 6;
    }
}

void clearN(int k){
    for (int i = 1; i<=9; i++)
        n[k][i] = false;
}

void SelectNum_Section(int k, int i, int j){
    for (int a = 0; a<3; a++){
        for (int b = 0; b<3; b++){
            int num = sudoku[section(i)+a][section(j)+b];
            n[k][num]=true;
        }
    }
}

void SelectNum_Cross(int k, int i, int j){
    for (int a = 0; a<9; a++){
        n[k][sudoku[a][j]] = true;
    }
    for (int a = 0; a<9; a++){
        n[k][sudoku[i][a]] = true;
    }
}

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

void view_num(int k){
    printf("\n=================\n");
    printf("n[%d]\n", k);
    for (int b = 1; b<=9; b++) printf("%d ", b);
    printf("\n");
    for (int b = 1; b<=9; b++) printf("%d ", n[k][b]);
    printf("\n=================\n");
}

void dfs(int k, int b){
    /*k(0부터 시작)와 blank_cnt(빈칸 개수)가 같아지면
    즉, 마지막 빈칸까지 채워지면 끝
    빈칸이 채워지는 조건이 항상 맞다는 가정하에 이렇게 품*/
    if (k==blank_cnt){
        view();
        exit(0); //<<<<<<<<<<<<질문하고자하는 부분
        return;
    }
    int i = b;
    while(blank[i].x!=-1 && blank[i].y!=-1){
        int x = blank[i].x;
        int y = blank[i].y;
        //현재 위치에서 십자로 없는 숫자를 n[k]에 true, false로 나타냄
        SelectNum_Cross(k,x,y);
        //현재 위치에서 같은 구역에 없는 숫자를 n[k]에 true, false로 나타냄
        SelectNum_Section(k,x,y);
        //view_num(k);
        int a;
        for (a = 1; a<=9; a++){
            //만약 해당 숫자가 안쓰였으면(십자, 해당구역에서)
            if (!n[k][a]){
                sudoku[x][y] = a;
                //view_num(k);
                //view();
                dfs(k+1,b+1);
                sudoku[x][y] = 0;
                //view_num(k);
                //view();
            }
        }
        if (a==10) {
            clearN(k);
            break;
        }
        else i++;
    }
}

int main(){
    blank_cnt = 0;
    for (int i = 0; i<9; i++){
        for (int j = 0; j<9; j++){
            scanf("%d", &sudoku[i][j]);
            
            //빈칸 위치를 배열로 나타냄
            if (!sudoku[i][j]) {
                blank[blank_cnt].x = i;
                blank[blank_cnt].y = j;
                blank_cnt++;
            }
        }
    }
    //마지막은 -1,-1
    if (blank_cnt==81) {
        blank[blank_cnt].x = -1;
        blank[blank_cnt].y = -1;
    }
    printf("\n");
    dfs(0, 0);
}

jjang36524 2년 전 1

dfs에서 정답이 만들어졌는지를 리턴하고, 어떤 숫자를 채웠을 때 정답이 만들어졌으면 바로 정답이 만들어졌음을 리턴하면 됩니다.

dltjr0703 2년 전 0

간단한 거였는데 어제 풀 때 스도쿠 푸는거 자체에만 너무 머리를 썼는지

생각을 못했네요

댓글 보자마자 해결했습니다 ㅎㅎ...

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

문제

문제

출처

ICPC

c언어 맞추긴 했는데 재귀함수 종료 조건을 잘 모르겠습니다

dltjr0703 2년 전 0

jjang36524 2년 전 1

dltjr0703 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말