어느정도 C++을 공부한 다음 코딩 활용도를 높이고 싶어 관련 문제를 찾아보았습니다.
그러다 아래의 링크에서 스도쿠 문제를 발견하였고 풀어보면 재밌겠다 생각하여 코딩을 해봤습니다.

codemate.kr

사실 위 사이트에도 답을 올려 놓았지만 velog에도 작성하면 좋을것 같아 포스팅을 해봅니다.

코드메이트에 올려놓은 풀이

0. 문제 분석 및 데이터 구조 생각하기

일단 스도쿠 문제를 간단화 해봅시다.

우리가 스도쿠를 정답인지 오답인지 판별하는 방법은 다음과 같습니다.

• 같은 행에서 겹치는 수가 있는가
• 같은 열에서 겹치는 수가 있는가
• 같은 블록(?)에서 겹치는 수가 있는가

간단히 생각해봐도 첫번째 조건과 두번째 조건은 판별하는 방식이 매우 비슷할 것 같습니다. 하지만 세번째 조건은 조금 다르게 생각해야 될 것 같습니다.

가로, 세로값을 판별하는 방식과 블록값을 판별하는 방식이 다를 것이므로 이 둘의 결과를 따로 집어넣는 방식이 좋겠습니다.

또한 스도쿠는 9 X 9 행렬처럼 이루어져 있기 때문에 직관적으로 int형 이중배열을 사용하는 것이 좋을 것 같습니다.

그래서 결국 만든 데이터 구조는 다음과 같습니다.

class Table{
    private :
    int array[9][9];

    bool first_result = true;           // 가로, 세로 확인한 결과
    bool second_result = true;          // 블록값 확인한 결과

}

Table 이라는 클래스를 만들었으니 당연히 생성자와 소멸자가 필요합니다.

또한 가로, 세로, 블록값을 판별하는 함수가 필요한데, 만약 이를 클래스 외부함수로 만들게 되면 함수를 호출할 때마다 Table 클래스의 정보를 항상 입력해야 됩니다.

이는 너무 귀찮을 것 같으므로 그냥 클래스 내부에 메소드를 만들도록 합시다.

class Table{
    private :
    int array[9][9];

    bool first_result = true;           // 가로, 세로 확인한 결과
    bool second_result = true;          // 블록값 확인한 결과

    public :
    Table(int (*input_array)[9]){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                array[i][j] = input_array[i][j];
            }
        }
    }
    Table(){}
    ~Table(){}

    bool check_row(int current_row);                        // 가로 확인하는 함수
    bool check_column(int current_column);                  // 세로 확인하는 함수
    bool check_block(int current_row, int current_column);  // 블록 확인하는 함수
    
    void total_check();   // 위 세 함수 같이 생각할 함수


    void print_array(){   // 내부 array print
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                std::cout << array[i][j] << " ";
            }
            std::cout << std::endl;
        }
    }
};

1. 같은 행에서 겹치는 수가 있는가

bool Table::check_row(int current_row){    // 가로값 확인하는 함수

    for (int i = 0; i < 9; i++){
        int first_value = array[current_row][i];

        for (int j = i + 1; j < 9; j++){
            if (first_value == array[current_row][j]) {return false;}
        }
    }

    return true;
}

한 행에서 겹치는 수가 있는지 판별하는 함수를 만들었습니다. 함수의 인자는 확인해볼 행 (int current_row) 입니다.

for 문을 돌리면서 배열 내에 first_value 와 같은 값이 있는지 확인합니다.
만약 같은 값이 있으면 return false로 바로 종료되게 만들었습니다.

first_value = array[current_row][i] 했으므로 first_value는 행의 첫번째, 두번째 ~~ 값으로 계속 변합니다.
또한 아래의 for 문에서 int j = i + 1 이라 했으므로 first_value 뒤의 값들만 확인합니다.

만약 중간에 first_value 와 같은값이 없으면 true 를 리턴합니다.

2. 같은 열에서 겹치는 수가 있는가

bool Table::check_column(int current_column){   // 세로값 확인하는 함수

    for (int i = 0; i < 9; i++){
        int first_value = array[i][current_column];

        for (int j = i + 1; j < 9; j++){
            if (first_value == array[j][current_column]) {return false;}
        }
    }

    return true;
}

앞서 말했듯이 세로값을 확인하는 함수는 앞의 함수와 거의 동일하게 돌아갑니다.

앞의 함수와 동일하게 first_value를 설정하였고 중간에 같은 값이 있으면 false를 리턴합니다.

3. 같은 블록에서 겹치는 수가 있는가

블록값을 확인할 때 주의할 점은 확인해야 되는 값이 앞의 함수처럼 바로 옆, 아래에만 존재하지 않는다는 점입니다. 하지만 이를 제외하면 무언가 동일하게 만들 수 있을 것 같습니다.

bool Table::check_block(int current_row, int current_column){   // 블록값 확인하는 함수

    // 이 함수는 각 블록값의 첫번째 원소의 row, column을 인수로 받음.

    for (int i = current_row; i < current_row + 3; i++){
        for (int j = current_column; j < current_column + 3; j++){
            
            // i, j 가 증가하면서 첫번째, 두번째 원소값 등 계속 올라감.
            int first_value = array[i][j];  

            int count = 0;
            // first_value와 같은 값을 같는 원소 수를 셈.

            for (int k = i; k < current_row + 3; k++){
                for (int l = j; l < current_column  + 3; l++){
                      // 만약 first_value와 같은 값이 있다면 count++
                    if (first_value == array[k][l]) {count++;}  
                }
            }

            /* 위의 k, l은 i, j 값과 같은 수부터 시작이므로 블록 내에 같은 값이 있다면 
            count 는 2 이상이 됨. 즉 first_value 와 같은 원소는 자기 자신밖에 없을 
            것이므로 count > 2 면 즉시 return false */
            if (count != 1) {return false;}
        }
    }

    // 아무 이상 없으면 return true
    return true;
}

확인해야 하는 값이 옆, 아래에만 있지 않기 때문에 check_block 함수는 현재의 형과 열 (int current_row, int current_column) 두가지 변수를 받습니다.

또한 위 두 값은 해당 블록의 첫번째 배열의 위치값을 넣도록 하였습니다.

즉, 아래와 같은 3가지 블록이 있을 때

1  2  3			4  2  1			7  8  9
4  5  6			3  5  7			1  2  3
7  8  9			6  8  9			4  5  6

첫번째 블록은 (1)이 위치한 값, 두번재는 (4), 세번째는 (7) 을 변수로 넣었다는 뜻입니다.

마지막으로 3, 4번째 for 문을 보면 k = i, l = j 부터 시작합니다.

for (int k = i; k < current_row + 3; k++){
   for (int l = j; l < current_column  + 3; l++){
       // 만약 first_value와 같은 값이 있다면 count++
      if (first_value == array[k][l]) {count++;} 
   }
}

위에서 first_value = array[i][j] 로 설정했기 때문에 for문이 돌아가면서 first_value 와 같은값이 한번은 나옵니다. 때문에 count != 1 일때는 false를 리턴하게 하였고 이상이 없으면 true를 리턴하게 하였습니다.

4. 종합해서 생각하기

이제 마지막 단계입니다. 위에서 만든 3가지 함수는 한 행 또는 열, 블록에서만 판별하는 함수였으므로, 모든 부분에 대해서 확인하는 부분을 만들어야 합니다.

void Table::total_check(){
    std::cout << std::endl;

    for (int i = 0; i < 9; i++){        // 일단 가로 확인
    	// first_result에 true or false 넣음
        first_result = check_row(i);    
        if (first_result == false) {std::cout << "False" << std::endl; return;}
    }
    for (int i = 0; i < 9; i++){        // 세로 확인
    	// first_result에 true or false 넣음
        first_result = check_column(i); 
        if (first_result == false) {std::cout << "False" << std::endl; return;}
    }

	/* 블록값 확인 : 각 블록값 첫번째 원소의 row(i), column(j) 을
    check_block 함수에 인자로 넣음*/
    for (int i = 0; i != 9; i += 3){    
        for (int j = 0; j != 9; j += 3){
            second_result = check_block(i,j);       
            // (i,j) : (0,0), (0,3), (0,6), (3,0) ~~ 이런식
            if (second_result == false) {std::cout << "False" << std::endl; return;}
        }
    }

    std::cout << "True" << std::endl;
}

각 for 문 속을 보면 결과값이 false 일 경우 바로 멈추도록 하였습니다.
또한 마지막 세번째 for 문을 보면 i += 3, j += 3 을 하였기 때문에 각 블록의 첫번째 위치값이 들어가게 됩니다.

(i,j) : (0,0), (0,3), (0,6), (3,0) ~~> (6,6) 

이제 지금까지 만든 것들을 종합해서 보면 아래와 같습니다.

#include <iostream>

class Table{
    private :
    int array[9][9];

    bool first_result = true;           // 가로, 세로 확인한 결과
    bool second_result = true;          // 블록값 확인한 결과

    public :
    Table(int (*input_array)[9]){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                array[i][j] = input_array[i][j];
            }
        }
    }
    Table(){}
    ~Table(){}

    bool check_row(int current_row);                        // 가로 확인하는 함수
    bool check_column(int current_column);                  // 세로 확인하는 함수
    bool check_block(int current_row, int current_column);  // 블록 확인하는 함수
    
    void total_check();                                     // 위 세 함수 같이 생각할 함수

    void print_array(){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                std::cout << array[i][j] << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main(){
    std::cout << "\ncode_start\n\n" << std::endl;
    
    int array[9][9];
    for (int i = 0; i < 9; i++){
        for (int j = 0; j < 9; j++){
            int temp;
            std::cin >> temp;
            array[i][j] = temp;
        }
        std::cout << std::endl;
    }
    
    Table test(array);
    test.print_array();

    test.total_check();
    
    std::cout << "\n\ncode_end\n" << std::endl;
    return 0;
}


bool Table::check_row(int current_row){		// 가로값 확인하는 함수

    for (int i = 0; i < 9; i++){
        int first_value = array[current_row][i];

        for (int j = i + 1; j < 9; j++){
            if (first_value == array[current_row][j]) {return false;}
        }
    }

    return true;
}
bool Table::check_column(int current_column){	// 세로값 확인하는 함수

    for (int i = 0; i < 9; i++){
        int first_value = array[i][current_column];

        for (int j = i + 1; j < 9; j++){
            if (first_value == array[j][current_column]) {return false;}
        }
    }

    return true;
}
bool Table::check_block(int current_row, int current_column){   
// 블록값 확인하는 함수

    // 이 함수는 각 블록값의 첫번째 원소의 row, column을 인수로 받음.

    for (int i = current_row; i < current_row + 3; i++){
        for (int j = current_column; j < current_column + 3; j++){
            
            int first_value = array[i][j];      
            // i, j 가 증가하면서 첫번째, 두번째 원소값 등 계속 올라감.

            int count = 0;
            // first_value와 같은 값을 같는 원소 수를 셈.

            for (int k = i; k < current_row + 3; k++){
                for (int l = j; l < current_column  + 3; l++){
	                // 만약 first_value와 같은 값이 있다면 count++
                    if (first_value == array[k][l]) {count++;}  
                }
            }

            /* 위의 k, l은 i, j 값과 같은 수부터 시작이므로 블록 내에 같은 값이 있다면 
            count 는 2 이상이 됨. 즉 first_value 와 같은 원소는 자기 자신밖에 없을 
            것이므로 count > 2 면 즉시 return false*/

            if (count != 1) {return false;}
        }
    }

    // 아무 이상 없으면 return true
    return true;
}

void Table::total_check(){
    std::cout << std::endl;

    for (int i = 0; i < 9; i++){        // 일단 가로 확인
        first_result = check_row(i);    // first_result에 true or false 넣음
        if (first_result == false) {std::cout << "False" << std::endl; return;}
    }
    for (int i = 0; i < 9; i++){        // 세로 확인
        first_result = check_column(i); // first_result에 true or false 넣음
        if (first_result == false) {std::cout << "False" << std::endl; return;}
    }

    for (int i = 0; i != 9; i += 3){    // 블록값 확인 : 각 블록값 첫번째 원소의 row(i), column(j) 을 check_block 함수에 인자로 넣음
        for (int j = 0; j != 9; j += 3){
            second_result = check_block(i,j);       
            // (i,j) : (0,0), (0,3), (0,6), (3,0) ~~ 이런식
            if (second_result == false) {std::cout << "False" << std::endl; return;}
        }
    }

    std::cout << "True" << std::endl;
}

5. 총평

처음 스도쿠 문제를 봤을 때 적절한 난이도일 것 같았는데 생각보다 쉬웠던 것 같습니다.
다음번에는 좀 더 적절한 문제를 가져와 봐야겠습니다. 감사합니다.