http://www.hackerschool.org/HS_Boards/zboard.php?id=Free_Lectures&no=1460 [º¹»ç]
#include<fstream>
using namespace std;
FILE *fin=fopen("input.txt", "r");
FILE *fout=fopen("output.txt", "w");
void back(int point);
int data[10][10];
int row_chk[10][10], col_chk[10][10];
int square_num[10][10], square_chk[10][10], square_cnt;
int zero_point[110][3], zero_cnt;
int main(){
int i, j, k, l;
for(i=1; i<=9; i+=3){
for(j=1; j<=9; j+=3){
square_cnt++;
for(k=i; k<i+3; k++){
for(l=j; l<j+3; l++){
square_num[k][l] = square_cnt; // 3*3 ¹è¿ Å©±â·Î °¢ »ç°¢Çü¿¡ ¹øÈ£¸¦ ºÎ¿©
}
}
}
}
for(i=1; i<=9; i++){
for(j=1; j<=9; j++){
fscanf(fin, "%d", &data[i][j]); // data[i][j] ¸¦ ÀԷ¹޴´Ù.
if(data[i][j]){
row_chk[i][data[i][j]]=1; // °¡·ÎÁ٠üũ ¹è¿¿¡ data[i][j] °¡ ¾²¿´´Ù´Â °ÍÀ» üũ
col_chk[j][data[i][j]]=1; // ¼¼·ÎÁ٠üũ ¹è¿¿¡ data[i][j] °¡ ¾²¿´´Ù´Â °ÍÀ» üũ
square_chk[square_num[i][j]][data[i][j]]=1; // »ç°¢Çü üũ ¹è¿¿¡ data[i][j] °¡ ¾²¿´´Ù´Â °ÍÀ» üũ
}
else{
zero_point[++zero_cnt][1] = i; // 0ÀÇ °³¼ö¸¦ ¼¼ÁÖ¸é¼ 0ÀÇ ÁÂÇ¥¸¦ ÀúÀåÇسõ´Â´Ù
zero_point[zero_cnt][2] = j;
}
}
}
back(0); // ¹éÆ®·¹Å· ½ÃÀÛ
fclose(fin);
fclose(fout);
return 0;
}
void back(int point){
int i, j;
int x, y;
if(point == zero_cnt){ // 0À» ¸ðµÎ ä¿ü´Ù¸é
for(i=1; i<=9; i++){
for(j=1; j<=9; j++){
fprintf(fout, "%d ", data[i][j]); // Ãâ·Â
}
fprintf(fout, "\n");
}
exit(0); // ´õ µ¹¸é ¾È µÇ´Ï±î Á¾·á
}
x = zero_point[point+1][1]; // point+1 ¹ø°ÀÇ 0ÀÇ ÁÂÇ¥¸¦ ¾ò¾î¿È
y = zero_point[point+1][2];
for(i=1; i<=9; i++){
if(!row_chk[x][i] && !col_chk[y][i] && !square_chk[square_num[x][y]][i]){ // data[x][y] ¿¡ ³ÖÀ» i°ªÀÌ ÀÌ¹Ì ¾²¿´´ø °ªÀÎÁö È®ÀÎ
row_chk[x][i] = col_chk[y][i] = square_chk[square_num[x][y]][i] = 1; // ¾²¿´´Ù°í üũ
data[x][y] = i; // data[x][y] ¿¡ °ªÀ» ä¿ö³Ö´Â´Ù.
back(point + 1); // ´ÙÀ½ 0À» ÇâÇØ ÀüÁø¤»
data[x][y] = row_chk[x][i] = col_chk[y][i] = square_chk[square_num[x][y]][i] = 0; // µ¹¾Æ¿À¸é¼ ÃʱâÈ(´ÙÀ½ ÀÛ¾÷À» À§ÇØ)
}
}
}
»ç¿ë¹ý
: exe ÆÄÀÏÀÌ ÀÖ´Â Æú´õ ¾È¿¡ input.txt ¿Í output.txt ¸¦ »ý¼ºÇØ ³õÀº ÈÄ
input ÆÄÀÏ ¾È¿¡ ½ºµµÄí Çü½ÄÀ¸·Î °ªÀ» ÀÔ·ÂÇØ ³õÀº ÈÄ ½ÇÇàÇÑ´Ù.
(ÀÔ·Â Çü½ÄÀº ºó ÄÀ» 0À¸·Î ä¿ö³Ö°í, ¶ç¾î¾²±â¸¦ ÇÏ¸é µË´Ï´Ù.)
¾Ë°í¸®Áò(?)
: ¹éÆ®·¹Å· ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇß½À´Ï´Ù.
°¡·ÎÁ٠üũ ¹è¿°ú ¼¼·ÎÁ٠üũ ¹è¿, 1¹ø ºÎÅÍ 9¹ø ±îÁöÀÇ Ã¼Å© ¹è¿À» ÀÌ¿ëÇؼ,
0À¸·Î üũµÈ ºñ¾îÀÖ´Â Ä¿¡ °ªÀ» Áý¾î³Ö°í ´ÙÀ½ ºóÄÀ¸·Î ÁøÇàÇÏ´Ù°¡, ´õ ÀÌ»ó ÁøÇàÇÒ ¼ö ¾ø´Ù°í ÆǴܵǴ °÷(³ÖÀ» °ªÀÌ ÇÑÁ¤µÇ¾î ÀÖÁö¸¸, ±× °ªµéÀÌ ¸ðµÎ üũ ¹è¿¿¡ ÀÌ¹Ì Ã¼Å©°¡ µÇ¾î ÀÖ´Â »óÅÂÀÏ ¶§)¿¡¼ return ÇØ µ¹¾Æ¿Í¼ ´Ù½Ã ´Ù¸¥ °ªÀ» Áý¾î³Ö´Â ½ÄÀ¸·Î ÇÏ¿´½À´Ï´Ù.
- ¿¹Àü¿¡ Á¤¿ÃÁغñÇÒ´ë Çß¾ú´ø °Çµ¥, ´Ù½Ã º¸´Ï »õ·Ó³×¿ä; Âü°í·Î ÀÌ°Ç À©µµ¿ìÀÇ Visual Studio C++ ȯ°æ¿¡¼ Á¦ÀÛÇÑ°Ì´Ï´Ù.
¿¹½Ã)
input)
4 0 5 0 0 0 8 0 0
3 9 0 0 0 0 5 0 0
1 0 0 0 0 0 0 0 2
0 0 0 0 0 4 0 0 0
6 8 0 0 0 0 0 0 1
2 0 0 0 9 1 0 0 0
0 0 0 4 5 0 0 9 0
0 0 2 0 0 0 3 0 0
9 1 0 0 8 0 0 0 4
output)
4 2 5 9 1 7 8 6 3
3 9 8 2 4 6 5 1 7
1 6 7 5 3 8 9 4 2
7 5 1 8 2 4 6 3 9
6 8 9 3 7 5 4 2 1
2 3 4 6 9 1 7 8 5
8 7 3 4 5 2 1 9 6
5 4 2 1 6 9 3 7 8
9 1 6 7 8 3 2 5 4
|
Hit : 20676 Date : 2010/05/24 01:02
|