글 읽기 - c++ 두 코드의 차이점

quddlr96 1년 전 0

제가 생각할 때는 visit 배열을 써서 효율성의 차이는 있을수 있지만 같은 결과가 나와야하는데

하나는 맞고 하나는 다릅니다. 이유가 궁금합니다 ㅜㅜ

//틀린 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int k;

vector<int> temp;
vector<int> num_list;
vector<bool> visit;
vector<vector<int>> result;

void dfs_conb(int num){
    if(num==6){
        sort(temp.begin(),temp.end());
        result.push_back(temp);
        return;
    }

    for(int i=0;i<num_list.size();i++){
        if(!visit[i]){
            temp.push_back(num_list[i]);
            visit[i] = true;
            dfs_conb(num+1);
            visit[i] = false;
            temp.pop_back();
        }
    }
}

void init(){
    temp.clear();
    result.clear();
    num_list.clear();
    for(int i=0;i<14;i++){
        visit[i]=false;
    }
}

void print_result(){
    for(int i=0;i<result.size();i++){
        for(int j=0;j<result[i].size();j++){
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int main(){
    
    while(1){
        cin >> k;
        if(k==0 || k<=6 || k >= 13) break;
        for(int i=0;i<k;i++){
            int x;
            cin >> x;
            num_list.push_back(x);
            visit.push_back(false);
        }
        dfs_conb(0);
        print_result();
        init();
    }
    return 0;
}


// 맞은 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int k;

vector<int> temp;
vector<int> num_list;
vector<bool> visit;
vector<vector<int>> result;

void dfs_conb(int start,int num){
    if(num==6){
        sort(temp.begin(),temp.end());
        result.push_back(temp);
        return;
    }

    for(int i=start;i<num_list.size();i++){
        if(!visit[i]){
            temp.push_back(num_list[i]);
            visit[i] = true;
            dfs_conb(i,num+1);
            visit[i] = false;
            temp.pop_back();
        }
    }
}

void init(){
    temp.clear();
    result.clear();
    num_list.clear();
    for(int i=0;i<14;i++){
        visit[i]=false;
    }
}

void print_result(){
    for(int i=0;i<result.size();i++){
        for(int j=0;j<result[i].size();j++){
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

int main(){
    
    while(1){
        cin >> k;
        if(k==0 || k<=6 || k >= 13) break;
        for(int i=0;i<k;i++){
            int x;
            cin >> x;
            num_list.push_back(x);
            visit.push_back(false);
        }
        dfs_conb(0,0);
        print_result();
        init();
    }
    return 0;
}

adung7 1년 전 0

위 코드는 dfs에서 조합을 구하는것이 아닌 순열을 구하고 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 두 코드의 차이점

quddlr96 1년 전 0

adung7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말