[Baekjoon] - 13단계 : 백트래킹

1. N과 M

#include <stdio.h>
#include <stdbool.h>

int arr[9] = {0,};
bool visited[9] = {false,};
int n,m;

void dfs(int count){
    if(count == m){
        for(int i=0;i<m;i++){
            printf("%d ",arr[i]);
        }
        printf("\n");
        
        return;
    }
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            visited[i] = true;
            
            arr[count] = i;
                      
            dfs(count+1);
            visited[i] = false;
        }
    }
}

int main(){
    scanf("%d %d",&n, &m);
    
    dfs(0);
}

2. N과 M (2)

#include <stdio.h>
#include <stdbool.h>

int arr[9] = {0,};
bool visited[9] = {false,};
int n,m;
bool check = false;//false이면 오름차순

void dfs(int count){
    if(check) {//추가
        check = false;
        return;
    }
    if(count == m){
        for(int i=0;i<m;i++){
            printf("%d ",arr[i]);
        }
        printf("\n");
        
        return;
    }
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            visited[i] = true;
            
            arr[count] = i;
            
            if(count != 0){//추가
                if(arr[count-1] > arr[count]){
                    check = true;
                }
            }
            
            dfs(count+1);
            visited[i] = false;
        }
    }
}

int main(){
    scanf("%d %d",&n, &m);
    
    dfs(0);
}

3. N과 M (3)

#include <stdio.h>
#include <stdbool.h>

int arr[9] = {0,};
int n,m;

void dfs(int count){
    if(count == m){
        for(int i=0;i<m;i++){
            printf("%d ",arr[i]);
        }
        printf("\n");
        
        return;
    }
    for(int i=1;i<=n;i++){
        arr[count] = i;
                      
        dfs(count+1);
    }
}

int main(){
    scanf("%d %d",&n, &m);
    
    dfs(0);
}

4. N과 M (4)

#include <stdio.h>
#include <stdbool.h>

int arr[9] = {0,};
int n,m;
bool check = false;//false이면 오름차순

void dfs(int count){
    if(check) {//추가
        check = false;
        return;
    }
    if(count == m){
        for(int i=0;i<m;i++){
            printf("%d ",arr[i]);
        }
        printf("\n");
        
        return;
    }
    for(int i=1;i<=n;i++){
        arr[count] = i;
        
        if(count != 0){//추가
            if(arr[count-1] > arr[count]){
                check = true;
            }
        }
        dfs(count+1);
    }
}

int main(){
    scanf("%d %d",&n, &m);
    
    dfs(0);
}

6. 스도쿠

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int board[10][10] = {0,};

bool possible(int row, int col, int num){//행,렬,3x3에서 공통적으로 남는수 여부
    
    for(int i=0;i<9;i++){// 행, 렬
        if(board[row][i] == num || board[i][col] == num)
            return false;
    }
    
    int row33 = (row / 3) * 3;
    int col33 = (col / 3) * 3;
    
    for(int i=row33;i<row33+3;i++){// 3x3
        for(int j=col33;j<col33+3;j++)
            if(board[i][j] == num)
                return false;
    }
    
    return true;
}

void sudoku(int row, int col){
    if(col == 9){
        sudoku(row+1, 0);
        return;
    }
    
    if(row == 9){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }
        exit(0);//return 쓰면 틀림
    }
    
    if(board[row][col] == 0){
        for(int i=1;i<=9;i++){
            if(possible(row, col, i)){
                board[row][col] = i;
                sudoku(row, col+1);
            }
        }
        board[row][col] = 0;//
        return;
    }
    
    sudoku(row, col+1);
}

int main(){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++)
            scanf("%d",&board[i][j]);
    }
    
    sudoku(0, 0);
}

7. 연산자 끼워넣기

#include <stdio.h>

int n;
int list[12] = {0,};
int min = 2100000000;
int max = -2100000000;
void dfs(int count, int value, int plus, int minus, int mul, int div){
    
    if(count == n){
        if(max < value) max = value;
        if(min > value) min = value;
        return;
    }
    else{
        if(plus > 0) dfs(count+1, value+list[count], plus-1, minus, mul, div);
        if(minus > 0) dfs(count+1, value-list[count], plus, minus-1, mul, div);
        if(mul > 0) dfs(count+1, value*list[count], plus, minus, mul-1, div);
        if(div > 0) dfs(count+1, value/list[count], plus, minus, mul, div-1);
    }
}
int main(){
    scanf("%d", &n);
    
    for(int i=0;i<n;i++) scanf("%d",&list[i]);
    
    int oper[5] = {0,};
    for(int i=0;i<4;i++) scanf("%d",&oper[i]);
    
    dfs(1, list[0], oper[0], oper[1], oper[2], oper[3]);
    
    printf("%d\n%d",max ,min);
}

요약

• 1번을 기준으로
• 2번은 오름차순 비교만 추가해주면된다.(주석)
• 3번은 방문여부조건을 지워주면된다.
• 4번은 방문조건 지우고 오름차순비교 추가한다.