글 읽기 - (C) 어떤 부분이 틀렸는 지 모르겠습니다..(장문, 스파게티코드)

jakeehoson 3년 전 0

여러번 시도해보다가 점점 길어지고 스파게티 코드가 돼서 질문 안드리고싶었지만..

여러가지 input도 시도해봐도 잘 나오는데 채점하면 틀립니다.

시도한 test set은 아래에 있습니다.

기본적인 로직은

1. cross hatching(나중에 이름을 알게돼서 코드에서 이름은 candidate입니다)

2. 빈칸에 들어갈 수가 하나밖에 없으면 채움

3. 위의 과정을 반복하고 더 이상 풀 수 없으면 빈칸에 들어갈 수가 2개(그것도 안되면 +1개)인 칸에 시도

...

이런 식입니다.

무조건 푼다는 오기로 질문할 걸 생각 못하고 짜서 가독성이 개판입니다 ㅠㅠ 죄송합니다.

(공지에서는 언급하지 말라 하셨지만 6%에서 틀립니다)

test set

//input 1
0 5 0 0 0 1 0 0 0
3 0 0 0 7 0 0 0 0
2 4 0 3 6 0 7 0 0
0 0 2 0 0 4 0 1 0
0 0 9 8 0 7 3 0 0
0 8 0 2 0 0 4 0 0
0 0 7 0 5 6 0 4 2
0 0 0 0 4 0 0 0 1
0 0 0 9 0 0 0 8 0
//output 1
7 5 6 4 8 1 2 9 3
3 9 8 5 7 2 1 6 4
2 4 1 3 6 9 7 5 8
5 7 2 6 3 4 8 1 9
4 6 9 8 1 7 3 2 5
1 8 3 2 9 5 4 7 6
8 3 7 1 5 6 9 4 2
9 2 5 7 4 8 6 3 1
6 1 4 9 2 3 5 8 7

//input 2
0 0 0 7 5 0 0 3 0
1 0 6 0 0 0 0 0 0
8 0 0 3 0 0 0 0 0
0 2 0 0 0 0 0 4 0
0 0 0 6 0 0 8 0 0
0 0 0 0 0 1 0 0 0
0 4 0 0 9 0 0 0 0
3 0 0 0 4 0 0 0 0
0 0 0 0 0 0 1 0 0
//output 2
2 9 4 7 5 8 6 3 1
1 3 6 9 2 4 7 5 8
8 7 5 3 1 6 4 9 2
7 2 1 5 8 9 3 4 6
4 5 3 6 7 2 8 1 9
9 6 8 4 3 1 5 2 7
6 4 7 1 9 5 2 8 3
3 1 2 8 4 7 9 6 5
5 8 9 2 6 3 1 7 4

//input 3 오래걸리지만 되긴 됩니다
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0
//output3
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

//input 4
0 0 0 6 3 0 2 0 7
8 0 0 0 0 0 0 0 0
0 0 0 7 0 0 0 0 0
0 0 2 0 0 5 0 0 0
0 0 0 0 4 0 0 8 0
0 7 0 0 0 0 0 0 0
1 0 0 2 0 0 5 0 0
0 3 0 0 0 0 0 4 0
4 0 0 0 0 0 0 0 0
//output4
5 9 4 6 3 8 2 1 7
8 6 7 4 2 1 3 5 9
2 1 3 7 5 9 8 6 4
6 4 2 8 7 5 9 3 1
3 5 1 9 4 2 7 8 6
9 7 8 1 6 3 4 2 5
1 8 6 2 9 4 5 7 3
7 3 9 5 8 6 1 4 2
4 2 5 3 1 7 6 9 8

//input5
0 0 5 3 0 0 0 0 0
8 0 0 0 0 0 0 2 0
0 7 0 0 1 0 5 0 0
4 0 0 0 0 5 3 0 0
0 1 0 0 7 0 0 0 6
0 0 3 2 0 0 0 8 0
0 6 0 5 0 0 0 0 9
0 0 4 0 0 0 0 3 0
0 0 0 0 0 9 7 0 0
//output5
1 4 5 3 2 7 6 9 8
8 3 9 6 5 4 1 2 7
6 7 2 9 1 8 5 4 3
4 9 6 1 8 5 3 7 2
2 1 8 4 7 3 9 5 6
7 5 3 2 9 6 4 8 1
3 6 7 5 4 2 8 1 9
9 8 4 7 6 1 2 3 5
5 2 1 8 3 9 7 6 4

//input6
9 0 3 6 0 1 4 0 7
0 0 0 0 8 0 0 0 0
6 0 0 9 0 7 0 0 2
4 0 6 0 0 0 1 0 8
0 3 0 0 0 0 0 7 0
7 0 8 0 0 0 2 0 3
5 0 0 7 0 2 0 0 4
0 0 0 0 6 0 0 0 0
3 0 1 8 0 9 7 0 6
//output6
9 8 3 6 2 1 4 5 7
2 7 4 3 8 5 9 6 1
6 1 5 9 4 7 3 8 2
4 5 6 2 7 3 1 9 8
1 3 2 4 9 8 6 7 5
7 9 8 5 1 6 2 4 3
5 6 9 7 3 2 8 1 4
8 2 7 1 6 4 5 3 9
3 4 1 8 5 9 7 2 6

//input7(blank)
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
//output7
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 6 7 4 8 9 5
8 7 5 9 1 2 3 6 4
6 9 4 5 3 8 2 1 7
3 1 7 2 6 5 9 4 8
5 4 2 8 9 7 6 3 1
9 6 8 3 4 1 5 7 2

//input8
0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
//output8
2 3 4 5 1 6 7 8 9
1 5 6 7 8 9 2 3 4
7 8 9 2 3 4 1 5 6
3 2 1 4 6 5 8 9 7
9 4 5 8 7 1 3 6 2
8 6 7 9 2 3 4 1 5
4 9 3 1 5 7 6 2 8
5 1 2 6 4 8 9 7 3
6 7 8 3 9 2 5 4 1

//input9
0 0 0 0 5 0 0 0 0
0 9 0 8 0 0 0 7 0
0 3 0 0 2 0 4 0 0
0 0 0 5 4 0 2 6 0
0 0 1 0 9 2 0 0 0
5 0 0 0 0 3 0 0 7
4 0 0 1 0 5 0 8 0
2 0 9 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
//output9
1 4 8 3 5 7 6 2 9
6 9 2 8 1 4 3 7 5
7 3 5 9 2 6 4 1 8
9 8 7 5 4 1 2 6 3
3 6 1 7 9 2 8 5 4
5 2 4 6 8 3 1 9 7
4 7 6 1 3 5 9 8 2
2 5 9 4 6 8 7 3 1
8 1 3 2 7 9 5 4 6

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


struct blank{                                     // 빈칸을 나타내는 구조체.
  int row;
  int col;
  int offset_row;
  int offset_col;
  bool possiblenums[9];
  int possiblecount;
};

int board[9][9];                                  // 현재 스도쿠 판.
int*** stack;                                     // 스도쿠 판들이 저장된 스택
int blankscounter = 0;                            // 처음 스캔한 보드에 빈 칸의 수 == 풀어야 하는 수
struct blank* blanks;                             // 빈칸들의 배열

bool is_valid(int row, int col, int x);           // board에서 (row, col) = x가 가능한지.
void blanks_valid_check();                        // board에서 blank들의 정보(possiblenums, count 등)를 업데이트 해줍니다.
bool fill_certains();                             // board에서 가정 없이 채울 수 있는 칸들을 채웁니다.
void printbaord();
int count_candidates(int row, int col, int x);    // board에서 (row, col) = x가 유일한지. 알고보니 cross hatching이라는 방법
bool board_validity_check();                      // 현재 board가 풀 수 있는 지.
void solve(int stack_index);                      // 실제 문제가 풀어지는 함수.



int main()
{
  int buffer;

  // read input
  for (int i = 0; i < 9; i++){
    for (int j = 0; j < 9; j++){
      scanf("%d",&buffer );
    if(buffer == 0){
      blankscounter++;
    }
    board[i][j] = buffer;
    }
  }
  blanks = (struct blank*)malloc(sizeof(struct blank) * blankscounter);
  int k = 0;

  // create stack
  stack = (int***)malloc(sizeof(int**) * blankscounter);
  for (int i = 0; i < blankscounter; i++){
    stack[i] = (int**)malloc(sizeof(int*) * 9);
    for (int r = 0; r < 9; r++){
      stack[i][r] = (int*)malloc(sizeof(int) * 9);
    }
  }

  // collect blanks info
  for (int i = 0; i < 9; i++){
    for (int j = 0; j <9; j++){
      if (board[i][j] == 0){
        blanks[k].row = i;
        blanks[k].col = j;
        blanks[k].offset_row = (i / 3) * 3;
        blanks[k].offset_col = (j / 3) * 3;
        k++;
      }
    }
  }

  memcpy(stack[0], board, sizeof(board));
  solve(0);

  return 0;
}

// check if x is valid in row, col
bool is_valid(int row, int col, int x){
  int offset_row = (row / 3) * 3;
  int offset_col = (col / 3) * 3;
  for (int i = 0; i < 9; i++){
    if (board[row][i] == x || board[i][col] == x){
      return false;
    }
  }
  for (int i = 0; i < 3; i++){
    for (int j = 0; j < 3; j++){
      if (board[offset_row+i][offset_col+j] == x){
        return false;
      }
    }
  }

  return true;
}

// update blanks possibility info
void blanks_valid_check(){

  int row, col, count;

  for (int i = 0; i < blankscounter; i++){
    row = blanks[i].row;
    col = blanks[i].col;
    count = 0;

    for (int x = 1; x <= 9; x++){
      if (is_valid(row,col,x)){
        blanks[i].possiblenums[x-1] = true;
        count++;
      }else{
        blanks[i].possiblenums[x-1] = false;
      }
    }

    blanks[i].possiblecount = count;
  }
}

bool fill_certains(){
  struct blank blanknow;
  bool flag = false;

  for (int i = 0; i < blankscounter; i++){

    blanknow = blanks[i];
  
    if(board[blanknow.row][blanknow.col] != 0){
      continue;
    }
    if(blanknow.possiblecount == 1){
      for (int x = 0; x < 9; x++){
        if (blanknow.possiblenums[x]){

          board[blanknow.row][blanknow.col] = x+1;
          flag = true;
          blanks_valid_check();
        }
      }

      continue;
    }
    
    
    for (int x = 0; x < 9; x++){
      if (is_valid(blanknow.row, blanknow.col, x+1) && count_candidates(blanknow.row, blanknow.col, x+1) == 1){
        
        board[blanknow.row][blanknow.col] = x+1;
        flag = true;
        blanks_valid_check();
        break;
        
      }
      
    }


  }

  return flag;
}

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

int count_candidates(int row, int col, int x){
  int rowcan = 0, colcan = 0, zonecan = 0, min;
  int offsetrow = (row/3) * 3, offsetcol = (col / 3) *3;
  for (int i = 0; i < 9; i++){
    if(board[row][i] == 0 && is_valid(row, i, x)){
      rowcan++;
    }
    if(board[i][col] == 0 && is_valid(i, col, x)){
      colcan++;
    }
  }
  for (int i = 0; i < 3; i ++){
    for (int j = 0; j < 3; j++){
      if (board[offsetrow + i][offsetcol + j] == 0 && is_valid(offsetrow + i, offsetcol + j, x)){
        zonecan++;
      }
    }
  }

  min = rowcan;
  if (min > colcan){
    min = colcan;
  }
  if ( min > zonecan){
    min = zonecan;
  }
  return min;
}

bool board_validity_check(){
  blanks_valid_check();
  for (int i = 0; i < blankscounter; i++){
    if(board[blanks[i].row][blanks[i].col] == 0 && blanks[i].possiblecount == 0){
      return false;
    }
  }
  return true;
}

void solve(int stack_index){
  
  memcpy(board, stack[stack_index], sizeof(board));
  int remain = 0;
  struct blank blanknow;

  //remain count

  while(fill_certains()){
    blanks_valid_check();
  }
  if(!board_validity_check()){
    //printf("this stack is not valid\n");
    return;
  }
  for (int i = 0; i < blankscounter; i++){
    blanknow = blanks[i];
    if(board[blanknow.row][blanknow.col] == 0){
      remain++;
    }
  }

  //printf("stack_index : %d\t(%d/%d)\n", stack_index, blankscounter- remain,blankscounter);
  

  memcpy(stack[stack_index], board, sizeof(board));

  if(board_validity_check()){
    if(remain == 0){
      //printf("solved at stack %d!!\n", stack_index);
      printbaord();
      exit(0);
    }else{
      for (int l = 2; l <= 9; l++){                             // 어떤 칸에 가능한 수의 종류가 l 이하면 시도해본다.
        for (int i = 0; i < blankscounter; i++){
          blanknow = blanks[i];
          if ( board[blanknow.row][blanknow.col] == 0 && blanknow.possiblecount <= l){
            for (int x = 0; x < 9; x++){
              if(blanknow.possiblenums[x]){

                board[blanknow.row][blanknow.col] = x+1;
                memcpy(stack[stack_index+1],board,sizeof(board));

                solve(stack_index+1);

                board[blanknow.row][blanknow.col] = 0;
                memcpy(board, stack[stack_index],sizeof(board));
              }
            }
          }
          
        }

      }
    }
  }else{
    if (remain == 0){ // 다 풀었지만 보드가 유효하지 않을때. 이론상 일어날 일이 없음.
      //printf("something went wrong");
      exit(1);
    }else{
      return;
    }
  }
}

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

문제

문제

출처

ICPC

(C) 어떤 부분이 틀렸는 지 모르겠습니다..(장문, 스파게티코드)

jakeehoson 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말