공부흔적

문제 링크

풀이 )

  빈칸에 해당되는 칸을 blank 벡터에 집어 넣는다.

  이후 빈칸을 한 칸씩 1부터 9까지 가능한 숫자를 check( )를 통해 확인하여 집어 넣는다.

  (9까지 모두 불가능하다면, 해당 경우는 종료)

  가능한 경우가 나오면 바로 출력하고 프로그램을 종료하기 위해 blank가 비었을 때 바로 출력하고 exit(0)을 호출한다.

#include <iostream>
#include <vector>

using namespace std;

int board[9][9];

bool check(int x, int y, int num){
    for(int r = 0; r < 9; ++r){
        if(board[r][y] == num)
            return false;
    }

    for(int c = 0; c < 9; ++c){
        if(board[x][c] == num)
            return false;
    }

    for(int r = x/3*3; r < x/3*3+3; ++r){
        for(int c = y/3*3; c < y/3*3+3; ++c){
            if(board[r][c] == num)
                return false;
        }
    }
    return true;
}

void dfs(vector<int>& blank){
    if(blank.empty()){
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                cout << board[i][j];
                if(j == 8)
                    cout << '\n';
                else
                    cout << ' ';
            }
        }
        exit(0);
    }

    int x = blank.back()/10;
    int y = blank.back()%10;
    blank.pop_back();
    for(int i = 1; i < 10; ++i){
        if(!check(x, y, i))
            continue;
        board[x][y] = i;
        dfs(blank);
        board[x][y] = 0;
    }
    blank.push_back(x*10+y);
}

int main(void){
    vector<int> blank;
    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            cin >> board[i][j];
            if(board[i][j] == 0)
                blank.push_back(i*10+j);
        }
    }

    dfs(blank);
}

문제 링크

풀이 )

  첫 행부터 시작해서 각 열에 들어갈 수 있는지(promise) 확인한 후, 들어간 후 다음 행에 대해서도 반복을 해 마지막 행까지 채워 넣는다.

  각 열에 들어갈 수 있는지 확인할 때에는 첫 행에서는 모든 열에 들어갈 수 있으므로 true를 반환하고,

  해당 행에 대해서 위쪽으로 양쪽 대각선과 열을 확인하여 위치할 수 없게 되는 경우 false를 반환한다.

#include <iostream>

using namespace std;

int n, ans;
int col[15];

bool promise(int r, int c){
    if(r == 0)
        return true;
    for(int i = 1; i <= r; ++i){
        if(col[r-i] == c || col[r-i] == c-i || col[r-i] == c+i)
            return false;
    }

    return true;
}

void dfs(int row){
    if(row == n){
        ans++;
        return;
    }
    for(int i = 0; i < n; ++i){
        if(!promise(row, i))
            continue;
        col[row] = i;
        dfs(row+1);
        col[row] = 0;
    }
}

int main(void){
    cin >> n;

    dfs(0);
    cout << ans;
    return 0;
}