글 읽기 - 스도쿠 dfs return

travis97 2년 전 0

dfs는 깊이 탐색으로 같은 깊이 면서 조건충족이 되는 다른경우의 수들은 return 하면서 새롭게 다른값도 들어가게 되잖아요.

이 문제의 경우, return 하는 경우는 언제인가요

4*4 스도쿠의 예제로 주시면 정말 감사하겠습니다

2143

4321

3412

1234

이렇게 생긴거에서 어디를 0으로 놔야 조건문 다 돌려도 못채워져서 return하고 되돌아갈 수 있을까요?

// [그 구역][그 값]이중배열을 이용한 그 구역엔 그 값은 있어!! 

#include<iostream>
#define MAX 9
using namespace std;
int map[MAX][MAX]; bool Row[MAX][MAX]; bool Col[MAX][MAX]; bool Square[MAX][MAX];

void dfs(int Cnt){
    int cy=Cnt/9; int cx= Cnt%9;
    
    if(Cnt==81) {for(int y=0;y<9;y++){
        for(int x=0;x<9;x++){
            cout<<map[y][x]<<" ";
        }
        cout<<"\n";}
        exit(0);}
        
    if(map[cy][cx]==0){
        for(int i=1;i<10;i++){
            if(Col[cx][i]||Row[cy][i]||Square[(cy / 3) * 3 + (cx / 3)][i]) continue;
            Col[cx][i]=1;Row[cy][i]=1;Square[(cy / 3) * 3 + (cx / 3)][i]=1;
            map[cy][cx]=i;
            dfs(Cnt+1);
            Col[cx][i]=0;Row[cy][i]=0;Square[(cy / 3) * 3 + (cx / 3)][i]=0;
            map[cy][cx]=0;
        }
    }
    else dfs(Cnt+1); //!!! 어떤 수가 이미 있어 그러면 cnt가 81을 향해가는건 알겠는데 이 의미가...
}
 
int main(void){
    ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    for (int y = 0; y < MAX; y++){
        for (int x = 0; x < MAX; x++){
            cin >> map[y][x];
            if (map[y][x] != 0){
                Row[y][map[y][x]] = true; //!!!그 구역에 map[y][x]=그값은 있어.  이렇게 해석 
                Col[x][map[y][x]] = true; Square[(y / 3) * 3 + (x / 3)][map[y][x]] = true;}}}
    dfs(0);
    return 0;}

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

문제

문제

출처

ICPC

스도쿠 dfs return

travis97 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말