c언어 2580번 스토쿠 (백준)

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

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

int a[82] = {0, };


void find(int x)
{
    if(x==81) { //스토쿠 완성! 출력
        for(int i = 0; i<81; i++) {
        printf("%d ", a[i]);
        if((i+1) % 9 == 0) printf("\n");//9개 출력 후 줄 바꿈
    }
    exit(0); //바로 프로그램 종료 //return 으로 하면 답이 여러개 출력 될 수 있음
    
    }
    
    
    if(a[x] == 0) { //수를 모른다면
        for(int i = 1; i<=9; i++)
        {
            int count = 0;
            a[x] = i; //1~9까지 집어넣음
            for(int j = (x/9)*9; j<(x/9)*9+9; j++) //가로
            {
                if(x != j && a[j] == a[x]) break; //가로상 같은 수가 있으면 정지
                count++;
            }
            for(int j = x%9; j<81 && count>=9; j=j+9) //세로
            {
                if(x != j && a[j] == a[x]) break; //세로상 같은 수가 있으면 정지
                count++;
            }
            
            
            int tmp = x/27; //가로 압축 
            int tmp_1 = (x%9)/3; //세로 압축 
            //9개의 3*3 영역이 만들어짐
            //각 영역의 시작점 0, 3, 6, 27, 30, 33, 54, 57, 60
            int start = 0;
            start = (tmp_1 * 3) + (tmp * 27);
            int t = 1;
            while(t<=9 && count>=18) //3*3사각형
            {
                    if(x != start) {
                        if(a[start] == a[x]) break; //사각형 내 같은게 있으면 멈춤
                    }
                    count++;
                    start++;
                    if(t%3==0) start = (start-3)+9;
                    t++;
                    
            }
            
            if(count == 27) { //하나도 같은게 없었다면
                find(x+1); //다음 껄로 넘어감
                a[x] = 0; //만약 돌아왔다면 다시 0으로
            } 
            a[x] = 0; //i=9까지 갔는데도 다 중복 될 경우 이전 루프로 돌아가지나, 0으로 바꾼 다음 가야함!!!!!!!
            
            
            count = 0;
            start = 0;
            t = 1;
        } 
        
    } else if(a[x] != 0) find(x+1);
}

int main(void)
{
    for(int i = 0; i<81; i++) scanf("%d", &a[i]);
   
    find(0);
    
    return 0;
}

 

• 풀이

1) 입력을 받는다.

2-1) 만약 입력받은 수가 0일 때 같은 줄에서 겹치는 게 있는지 확인하고 없다면 수를 집어넣는다.

수는 1~9까지 for문을 이용하여 먼저 대입 후 비교했다. 

3) 2-1)에서 가로 상에서 비교했다면, 이번에는 세로 상에서 비교한다. 

4) 여기선 3*3 네모에서 겹치는지를 확인한다.

5) 겹치지 않는다면(count == 27) 재귀, 겹치면(count<27) 다음 수로,

다 겹쳤으면 다시 이전 재귀함수로 알아서 돌아간다. (단 반드시 겹쳤을 경우 0으로 반드시 초기화 해줘야 한다)

 

2-2) 만약 입력받은 수가 0이 아니라면 바로 다음 걸로 넘어간다. //find(x+1);

 

6)모든 수를 다 입력하고 나면 x 는 81이 된다.

여기선 그 모든 수를 형식에 맞게 출력하면 된다.

그런 다음 exit(0);으로 프로그램을 종료한다.

return;을 사용하게 되면 find(81)만을 종료하게 되며, find(80)부터 이어하게 된다.

이럴 경우 새로운 답을 찾아서 출력 할 수 도 있게 된다.