[단계 13] 백트래킹 (8문제)

backtracking

: 퇴각검색

: 한정 조건을 가진 문제를 푸는 전략

: 조합탐색과 연관

 

www.acmicpc.net/step/34

백트래킹 단계

 

● [문제번호 15649] N과 M(1)

#include <iostream>

using namespace std;

int N, M;
int num[9] = {0, };			// 초기화 하면 4ms 실행시간 감소
bool visited[9] = {0, };

void dfs(int cnt)
{
    if(cnt == M)
    {
        for(int i = 0; i < M; i++)
            cout << num[i] << ' ';
        cout << '\n';				// endl 사용시 시간 초과 판정
        return ;
    }
    
    for(int i = 1; i <= N; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            num[cnt] = i;
            dfs(cnt + 1);
            visited[i] = false;
        }
    }
}


int main()
{
    cin >> N >> M;
    
    dfs(0);

    return 0;
}

 

● [문제번호 15650] N과 M(2)

#include <iostream>

using namespace std;

int N, M;
int num[9] = {0, };                 // 초기화 하면 4ms 실행시간 감소
bool visited[9] = {0, };

void dfs(int cnt, int cnt_num)
{
    if(cnt == M)
    {
        for(int i = 0; i < M; i++)
            cout << num[i] << ' ';
        cout << '\n';               // endl 사용시 시간 초과 판정
        return ;
    }
    
    for(int i = cnt_num; i <= N; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            num[cnt] = i;
            dfs(cnt + 1, i + 1);
            visited[i] = false;
        }
    }
}


int main()
{
    cin >> N >> M;
    
    dfs(0, 1);

    return 0;
}

 

● [문제번호 15651] N과 M(3)

#include <iostream>

using namespace std;

int N, M;
int num[9] = {0, };                 // 초기화 하면 4ms 실행시간 감소

void dfs(int cnt)
{
    if(cnt == M)
    {
        for(int i = 0; i < M; i++)
            cout << num[i] << ' ';
        cout << '\n';               // endl 사용시 시간 초과 판정
        return ;
    }
    
    for(int i = 1; i <= N; i++)
    {
        num[cnt] = i;
        dfs(cnt + 1);
    }
}


int main()
{
    cin >> N >> M;
    
    dfs(0);

    return 0;
}

 

● [문제번호 15652] N과 M(4)

#include <iostream>

using namespace std;

int N, M;
int num[9] = {0, };                 // 초기화 하면 4ms 실행시간 감소

void dfs(int cnt, int cnt_num)
{
    if(cnt == M)
    {
        for(int i = 0; i < M; i++)
            cout << num[i] << ' ';
        cout << '\n';               // endl 사용시 시간 초과 판정
        return ;
    }
    
    for(int i = cnt_num; i <= N; i++)
    {
        num[cnt] = i;
        dfs(cnt + 1, i);
    }
}


int main()
{
    cin >> N >> M;
    
    dfs(0, 1);

    return 0;
}

 

● [문제번호 9663] N-Queen

#include <iostream>

using namespace std;

int N, result;
int num[15];
                // 배열의 value : 행
                // 배열의 index : 열

bool check(int col)
{
    for(int i = 0; i < col; i++)
    {                               // 다른 열이니 열 비교 X
        if(num[col] == num[i])      // 행 비교
            return false;
        else if(col - i == abs(num[col] - num[i]))  // 대각선 비교
            return false;
    }
    return true;
}

void dfs(int col)
{
    if(col == N)
        result++;
    else
    {
        for(int row = 0; row < N; row++)
        {
            num[col] = row;
            
            if(check(col))
                dfs(col + 1);
        }
    }
}


int main()
{
    cin >> N;
    
    dfs(0);
    
    cout << result;

    return 0;
}

 

● [문제번호 2580] 스도쿠

 

 

● [문제번호 14888] 연산자 끼워넣기

 

 

● [문제번호 14889] 스타트와 링크