글 읽기 - 2580번 스도쿠 질문입니다.

ljy8947 8년 전 0

Q2.

정답대로 나오는데, 오답인 이유를 모르겠습니다. <-- 이렇게 쓰면 삭제될 수도 있다고 공지글을 읽었습니다만, 고민을 해 보아도 답이 안나와서요..

입력의 조건 중 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다는 따로 고려하지 않았습니다.

출력의 조건 중 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만 출력한다는 조건의 경우에는 아래와 같은 스도쿠를 이용하여 구현해 보았습니다.

9 2 6 5 7 1 4 8 3
3 5 1 4 8 6 2 7 9
8 7 4 9 2 3 5 1 6
5 8 2 3 6 7 1 9 4
1 4 9 2 5 8 3 6 7
7 6 3 1 0 0 8 2 5 <-- 0에 같은 행 내에 없는 숫자를 찾아서 대입 후 다시 정답을 도출하는 방식.
2 3 8 7 0 0 6 5 1
6 1 7 8 3 5 9 4 2
4 9 5 6 1 2 7 3 8

일단 위의 복수의 정답이 존재하는 스도쿠는 잘 풀리는데, 이러한 방식이 맞는지 궁금합니다.

Q3. 9칸 정방형을 다루는 방법을 잘 모르겠습니다. 그래서 아래 코드와 같이 노가다 방법으로 했는데, 적절한 방법을 알려주시면 감사하겠습니다.

Q4. 해결. yukariko님 감사합니다.

#include <stdio.h>

int arr[9][9]; // 스도쿠를 저장할 이차원 배열
int h_sum[9], v_sum[9], s_sum[9]; // 가로, 세로, 9칸 정사각형의 합을 저장할 배열.
int h_zero_num[9], v_zero_num[9], s_zero_num[9]; // 가로, 세로, 9칸 정사각형의 0의 개수를 저장할 배열

void get_info(); // 가로, 세로, 9칸 정사각형의 합과 0의 개수를 새로 갱신하는 함수
void fill_one_zero(); // 가로, 세로의 정보를 이용하여 0을 알맞은 숫자로 치환하는 함수
void fill_square(); // 9칸 정사각형의 정보를 이용하여 0을 알맞은 숫자로 치환하는 함수
int more_than_two(); // 정답이 두 가지 이상인 스도쿠에 대한 함수

int main()
{
    int i, j;

    for(i=0; i<9; i++) //입력
    {
        for(j=0; j<9; j++)
            scanf("%d", &arr[i][j]);
    }

   for(i=0; i<9; i++)// 주어진 예제를 풀 때 가로와 세로를 먼저 채우고, 정보를 갱신하고, 다시 정사각형을 채우고 하는 식으로 한 것에 입각. 반복횟수 9번은 임의의 숫자입니다.
   {
        for(j=0; j<9; j++)
        {
            get_info();
            fill_one_zero();
            get_info();
            fill_square();
        }
        if(more_than_two!=0) more_than_two(); // 정답이 두개인 스도쿠인 경우, 하나의 0에 중복되지 않는 숫자를 넣어준 후 다시 돌립니다.
    }

    for(i=0; i<9; i++) // 출력
    {
        for(j=0; j<9; j++)
        {
            printf("%d ", arr[i][j]);
        }
    }

    return 0;
}

void get_info()
{
    int i, j;

    for(i=0; i<9; i++) // 정보 갱신 전 0으로 초기화
    {
        h_sum[i]=0;
        v_sum[i]=0;
        s_sum[i]=0;

        h_zero_num[i]=0;
        v_zero_num[i]=0;
        s_zero_num[i]=0;
    }

    for(i=0; i<9; i++)
    {
        for(j=0; j<9; j++)
        {
            h_sum[i]+= arr[i][j]; //가로 각 줄의 합을 구함.
            v_sum[j]+= arr[i][j]; // 세로 각 줄의 합을 구함.

            if(i<3 && j<3) s_sum[0]+= arr[i][j]; //9칸 정방형 들의 합을 구함. 이런 노가다 방법 말고, 깔끔한 방법은 혹시 없나요?
            else if(i<3 && j>=3 && j<6) s_sum[1]+= arr[i][j];
            else if(i<3 && j>=6) s_sum[2]+= arr[i][j];

            else if(i>=3 && i<6 && j<3) s_sum[3]+= arr[i][j];
            else if(i>=3 && i<6  && j>=3 && j<6) s_sum[4]+= arr[i][j];
            else if(i>=3 && i<6 && j>=6) s_sum[5]+= arr[i][j];

            else if(i>=6 && j<3) s_sum[6]+= arr[i][j];
            else if(i>=6 && j>=3 && j<6) s_sum[7]+= arr[i][j];
            else s_sum[8]+= arr[i][j];


            if(arr[i][j]==0) // 가로, 세로, 9칸 정방형의 0의 개수 정보 갱신.
            {
                h_zero_num[i]++;
                v_zero_num[j]++;

                if(i<3 && j<3) s_zero_num[0]++;
                else if(i<3 && j>=3 && j<6) s_zero_num[1]++;
                else if(i<3 && j>=6) s_zero_num[2]++;

                else if(i>=3 && i<6 && j<3) s_zero_num[3]++;
                else if(i>=3 && i<6  && j>=3 && j<6) s_zero_num[4]++;
                else if(i>=3 && i<6 && j>=6) s_zero_num[5]++;

                else if(i>=6 && j<3) s_zero_num[6]++;
                else if(i>=6 && j>=3 && j<6) s_zero_num[7]++;
                else s_zero_num[8]++;
            }
        }
    }
}

void fill_one_zero() // 가로와 세로의 정보를 이용하여 스도쿠 값을 알맞게 치환.
{
    int i, j;

    for(i=0; i<9; i++)
    {
        for(j=0; j<9; j++)
        {
            if(arr[i][j]==0 && h_zero_num[i] ==1)
                arr[i][j]= 45-h_sum[i];
            if(arr[i][j]==0 && v_zero_num[j] ==1)
                arr[i][j]= 45-v_sum[j];
        }
    }
}

void fill_square() // 9칸 정방형의 정보를 이용하여 스도쿠 값을 알맞게 치환.
{
    int i, j;

    for(i=0; i<9; i++)
    {
        for(j=0; j<9; j++)
        {
            if(s_zero_num[i]==1 && arr[i][j]==0)
            {
                if(i<3 && j<3) arr[i][j]= 45-s_sum[0];
                else if(i<3 && j>=3 && j<6) arr[i][j]= 45-s_sum[1];
                else if(i<3 && j>=6) arr[i][j]= 45-s_sum[2];

                else if(i>=3 && i<6 && j<3) arr[i][j]= 45-s_sum[3];
                else if(i>=3 && i<6  && j>=3 && j<6) arr[i][j]= 45-s_sum[4];
                else if(i>=3 && i<6 && j>=6) arr[i][j]= 45-s_sum[5];

                else if(i>=6 && j<3) arr[i][j]= 45-s_sum[6];
                else if(i>=6 && j>=3 && j<6) arr[i][j]= 45-s_sum[7];
                else arr[i][j]= 45-s_sum[8];
            }
        }
    }
}

int more_than_two() // 정답이 두 가지 이상인 스도쿠에 대한 함수.
{
    int i, j, m, n;
    int find=0; 
    int tmp[9][9]={};

    for(i=0; i<9; i++)
    {
        for(j=0; j<9; j++)
        {
            if(arr[i][j]==0) // 스도쿠의 정답 찾기 함수들을 돌린 후에도 0이 발견되면 정답이 두 가지 이상이라는 판단.
            {
                m=i;
                n=j;
                ++find;
                break;
            }
        }
        if(find!=0)
        {
            tmp[m][n]=1; //0이 발견된 경우 1을 넣고 탈출.
            break;
        }
    }

    if(find!=0)
    {
        for(i=0; i<9; i++)
        {
            for(j=0; j<9; j++)
            {
                if(tmp[m][n]==arr[m][j]) tmp[m][n]++; //같은 행 내에 똑같은 숫자가 있을 경우 1씩 증가시키면서 중복을 검사.
            }
        }
        arr[m][n]=tmp[m][n];
    }
    return find;
}

yukariko 8년 전 0

Q1과 Q4에 대해서만..

Q1.

터미널에서 작성하신다면 다음의 방법이 있겠죠.

input.txt 에다 테스트 데이터를 넣고 저장한 다음

cat input.txt | ./test

를 이용하면 input.txt의 내용이 test의 표준입력으로 들어갈 것입니다.

그리고 터미널에서도 shift + insert 키로 붙여넣기가 가능한것으로 알고있습니다.

Q4.

함수를 작성할 때, 특히 재귀 함수인 경우 인자에 넣어야할 변수가 많다면

코딩도 불편하고, 스택 메모리를 더 사용하게 되죠. 문제를 풀때는 전역변수를 자주 사용하는 편이고

그로인한 감점같은것은 없습니다.

ljy8947 8년 전 0

감사합니다

baekjoon 8년 전 0

A2. 지금 스도쿠를 푸는 방법이 Cross-hatching 방법인데, 이 방법만으로는 스도쿠를 풀 수 없는 경우가 나타날 수 있습니다. (https://www.acmicpc.net/problem/2955)

그래서, 백트래킹을 이용해서 풀어야 합니다.

A3. 9칸 정방형이 3*3크기의 정사각형을 말하는 것 같은데, 9*9칸을 3*3개의 큰 정사각형으로 나누고 있습니다.

일반적인 배열을 이용하는 것과 비슷하게 생각하면, 차례대로

0 1 2
3 4 5
6 7 8

로 정사각형 번호를 생각할 수 있습니다.

배열처럼 생각하면 가장 윗 정사각형이 있는 곳이 0행, 가장 오른쪽 정사각형이 있는 곳이 2열이 되지요.

따라서, (i,j)는 (i/3)*3 + (j/3) 번 정사각형에 들어가게 됩니다.

이 방법은 자신의 페이스북에 스도쿠 푸는 프로그램을 올린 싱가포르 리센룽 총리의 프로그램에서도 찾아볼 수 있습니다.

https://www.facebook.com/leehsienloong/photos/a.344710778924968.83425.125845680811480/905828379479869/

baekjoon 8년 전 0

그리고 @ljy8947 처럼 언급도 할 수 있습니다.

ljy8947 8년 전 0

@baekjoon 감사합니다. 확실히2239번의 스도쿠 input을 넣어보니 0이 하나도 채워지지 않네요.

백트레킹을 좀 더 공부하고 다시 도전해 봐야겠습니다.

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

문제

문제

출처

ICPC

2580번 스도쿠 질문입니다.

ljy8947 8년 전 0

yukariko 8년 전 0

ljy8947 8년 전 0

baekjoon 8년 전 0

baekjoon 8년 전 0

ljy8947 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말