algorithm/problem solving

acmicpc.net 2580(백트래킹), 2239(백트래킹)

qkqhxla1 2016. 10. 7. 14:03

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


파이썬으로 짰는데 시간초과가 났다........ c로 다시 짜니까 됬다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
 
int sudoku[9][9];
bool global_end_flag = false;
 
void check(int row,int col,int t_sudoku[][9])
{
    int _sudoku[9][9];
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            _sudoku[i][j] = t_sudoku[i][j];
 
    if(global_end_flag) return;
    for(int n=1;n<10;n++)
    {
        bool flag = true;
        for(int i=0;i<9;i++)
            if(_sudoku[row][i]==n || _sudoku[i][col]==n)
            {
                flag = false;
                break;
            }
        if(!flag) continue;
        int r = int(row/3)*3, c = int(col/3)*3;
        for(int i=r;i<r+3;i++)
        {
            for(int j=c;j<c+3;j++)
                if(_sudoku[i][j]==n)
                {
                    flag = false;
                    break;
                }
            if(!flag) break;
        }
        if(!flag) continue;

        _sudoku[row][col] = n;
 
        flag = false;
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
                if(_sudoku[i][j]==0)
                {
                    check(i,j,_sudoku);
                    flag = true;
                    break;
                }
            if(flag) break;
        }
    }
    bool end_flag = true;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            if(_sudoku[i][j]==0)
            {
                end_flag = false;
                break;
            }
        if(!end_flag) break;
    }
    if(end_flag)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
                printf("%d ",_sudoku[i][j]);
            printf("\n");
        }
        global_end_flag = true;
        return;
    }
}
  
int main()
{
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
            scanf("%d",&sudoku[i][j]);
    bool flag = false;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
            if(sudoku[i][j]==0)
            {
                check(i,j,sudoku);
                break;
            }
        if(flag) break;
    }
    return 0;
}

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


똑같은 스도쿠 문제. 입력부를 아래처럼 바꾸고 출력시 공백을 없애주면 된다.

for(int i=0;i<9;i++)
	{
		string input;
		getline(cin,input);
		for(int j=0;j<9;j++)
			sudoku[i][j] = input[j]-48;
	}