백준로고

[문제 링크]

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

[입출력 예]

입력 출력
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0		 1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

[소스코드]

//14:54
#include <bits/stdc++.h>
using namespace std;

int board[9][9];
pair<int,int> arr[81];
int arrSize;
bool isPrinted = false;


void print_board(){

    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout<<board[i][j]<<' ';
        }
        cout<<'\n';
    }
}

void print_arr(){
  cout<<"[";
  for(int i=0; i<arrSize; i++){
    pair<int,int> cur = arr[i];
    cout<<"("<<cur.first<<","<<cur.second<<"), ";
  }
  cout<<"]";
}

bool check(int x, int y){
  int row[10] = {};
  int col[10] ={};
  int square[10]={};
  for(int j=0; j<9; j++){
    row[board[x][j]]++;
    if (board[x][j]>0 && row[board[x][j]]>1) return false;
  }

  for (int i=0; i<9; i++){
    col[board[i][y]]++;
    if (board[i][y]>0 && col[board[i][y]]>1) return false;
  }

  int start_i = (x/3)*3;
  int start_j = (y/3)*3;

  for (int i=0; i<3; i++){
    for (int j=0; j<3; j++){
      square[board[start_i+i][start_j+j]]++;
      if(board[start_i+i][start_j+j]>0 && square[board[start_i+i][start_j+j]]>1)return false;
    }
  }
  return true;
}

void func(int k){
  if (isPrinted)return;
  if(k==arrSize){
    if(!isPrinted){

     print_board();
    isPrinted=true;
    }
    return;
  }

  int k_i = arr[k].first;
  int k_j = arr[k].second;

  for (int i=1; i<=9; i++){
    board[k_i][k_j]=i;
    if (check(k_i,k_j)){
      func(k+1);
    }
    board[k_i][k_j]=0;
  }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i=0 ; i<9; i++){
        for (int j=0; j<9; j++){
            cin>>board[i][j];
            if(board[i][j]==0){arr[arrSize]={i,j};
            arrSize++;}
        }
    }

    func(0);

    return 0;
}
 
 
 
 

'PS > BOJ' 카테고리의 다른 글

백준 1759 암호만들기 C++  (0) 2022.02.18
백준 1920 수 찾기 파이썬  (0) 2022.02.18
백준 1182 부분수열의 합 파이썬 풀이  (0) 2022.02.12
백준 2178 미로탐색 C++  (0) 2022.02.10
백준 3055번 탈출 파이썬  (0) 2022.02.09

티스토리툴바