JArchive 프로그래밍 일기

문제

주사위 세개

"맞았습니다." 코드 

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 백준 2480 주사위 세개

vector<int> v(3);
int result;

void func(){

    sort(v.begin(), v.end());

    if(v[0] == v[2]) { // 셋 다 같은 수
        cout << 10000 + (1000 * v[0]);
    }
    else if((v[0] == v[1]) || (v[1] == v[2])) { // 2개가 같은 수. 항상 공통인 숫자는 2번째 숫자.
        cout << 1000 + (v[1] * 100) ;
    }
    else{ // 셋 다 서로 다른 수
        cout << v[2] * 100;
    }
}

void input(){
    cin >> v[0] >> v[1] >> v[2];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    func();

    return 0;
}

리뷰

조건식을 잘못써서 처음에 틀렸다. 

틀린 코드는 아래와 같다. 

if((v[0] == v[1]) == v[2]) { // 셋 다 같은 수
    result = 10000 + (1000 * v[0]);
}

틀린 이유는 숫자끼리 비교해야하는데, true와 숫자를 비교했기 때문이다. 

주사위 숫자가 1 1 3 일때, 1 과 1은 같으니까 참이 나온다. 

따라서 1과 3을 비교하게 되는게 아니라, 

true와 3을 비교하게 되므로 항상 true가 나온다. 그래서 틀렸다. 

고쳐서 맞은 코드는 아래와 같다.

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

// 백준 2480 주사위 세개

vector<int> v(3);
int result;

void func(){

    sort(v.begin(), v.end());

    if((v[0] == v[1]) && (v[1] == v[2])) { // 셋 다 같은 수
        result = 10000 + (1000 * v[0]);
    }
    else if((v[0] == v[1]) && (v[1] != v[2])) { // 앞쪽 2개가 같은 수
        result = 1000 + (v[0] * 100) ;
    }
    else if((v[0] != v[1]) && (v[1] == v[2])) { // 뒤쪽 2개가 같은 수
        result = 1000 + (v[1] * 100) ;
    }
    else{ // 셋 다 서로 다른 수
        result = v[2] * 100;
    }
    cout << result;
}

void input(){
    cin >> v[0] >> v[1] >> v[2];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    func();

    return 0;
}

좀더 깔끔한 코드는 아래와 같다. 

일단 정렬을 한다. 

셋 다 같은 수라면, 첫번째 숫자와 세번째 숫자가 같을 것이다. 

    if(v[0] == v[2]) { // 셋 다 같은 수
        cout << 10000 + (1000 * v[0]);
    }

같은 수가 2개라면, 1번째 2번째가 같거나. 2번째와 3번째가 같을 것이다. 

두 조건 모두 가운데 숫자가 공통으로 들어간다. 

    else if((v[0] == v[1]) || (v[1] == v[2])) { // 2개가 같은 수. 항상 공통인 숫자는 2번째 숫자.
        cout << 1000 + (v[1] * 100) ;
    }

바킹독님 코드 참고 

바킹독님의 코드를 보고 나니깐 벡터를 안써도 됬겠구나 싶었다. 

정렬하지 않고, 숫자 두 개가 같은 경우는 3가지 다.

1째와 2째를 비교. 2째와 3째를 비교. 1째와 2째를 비교. 

셋 다 다른 수일 때는, max() 함수를 쓴 것이 좋았다. 

문제

BFS 스페셜 저지

리뷰

입력으로 정점의 순서가 주어진다.

그 순서가 BFS로 탐색할 때 나올 수 있는 방문 순서인가를 확인하는 문제다.

순서가 올바르지 않다는 것은, 접근해서는 안되는 차례에 방문했다는 것이다.

시작점은 반드시 1이어야한다.

큐에 넣는 순서는 input list 에 맞춰서 BFS를 진행해야 한다.

코드

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

// BFS 스페셜 저지 (BOJ 16940) 

int N; // 정점 개수 
vector<int> B[100001]; // 인접리스트 
int visited[100001]; // 방문 체크 
queue<int> q, input_q;

int BFS(){

    while(!q.empty()){
        int current = q.front(); 
        q.pop();

        set<int> s; // 중복제외하고 정점 번호 저장할 set  

        for(int i : B[current]){ // 현재 노드의 인접 정점들이 있는지 확인   
            if(visited[i]) continue; // 이미 방문한것 제외
            visited[i] = true; // 방문표시  
            s.insert(i); // 방문 해야할 것들 set에 저장  
        }

        // input_q 순서 따라가기
        for(int i = 0; i < (int)s.size(); i++){
            if(input_q.empty()) return false; // 방문 할 정점 없음 종료  

            int candidate = input_q.front(); // 지금 방문할 순서의 정점
            input_q.pop();

            // 후보가 set에 없다면, 지금 방문할 순서의 정점이 현재정점과 인접하지 않으므로 종료.  
            if(s.find(candidate) == s.end()) return false;
            else q.push(candidate);
        }
    }

    return true;        
}

bool solve(){

    int first = input_q.front(); 
    input_q.pop();
    if(first != 1) return false; // 시작 정점은 1이어야 한다  

    visited[first] = true;

    q.push(first); // 방문했으니까 큐에 넣는다 

    bool answer = BFS(); // BFS 탐색 시작  

    return answer;
}

void input(){ // 문제의 입력받는다  

    cin >> N; // 정점 개수  
    int a=0, b=0; 

    for(int i = 1; i < N; i++){ // N-1개의 인접리스트 정보   
        cin >> a >> b;
        B[a].push_back(b);
        B[b].push_back(a);
    }

    for(int i = 0; i < N; i++){ // 주어진 방문 순서를 전부 큐에 넣는다  
        cin >> a;
        input_q.push(a);
    }
}

int main() {    

     input();
     bool answer = solve();  
     cout << answer;

    return 0;
} 

문제

N과M(5) 백준 15654번

리뷰

1부터 N까지의 자연수가 아니라, 입력받은 N개의 수열을 이용한다.

중복을 허용하지 않고 2개 고르는 것이라서 중복체크를 위해 ch [10] 배열이 필요하다.

수열은 사전 순으로 증가하는 순으로 출력해야 하니까, 입력받자마자 sort() 했다.

코드

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

// n과 m  (5)

int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.  
int arr[10]; // 입력받은 수열 저장.
int ch[10]; // 중복을 허용하지 않으니까, 체크 배열이 필요하다.
int answer[10];

void go(int index){

    if(index == M){
        for(int i = 0; i < M; i++){
            printf("%d ", answer[i]);
        }
        cout << '\n';
        return;
    }

    for(int i = 0; i < N; i++){
        if(ch[i]) continue;

        ch[i] = 1;
        answer[index] = arr[i];
        go(index+1);
        ch[i] = 0;
    }
}

int main(void){

    cin >> N >> M;

     for(int i = 0; i < N; i++){
         scanf("%d", &arr[i]);
    }

    sort(arr, arr+N);

     go(0);

    return 0;
}

문제

N과M(6) 백준 15655번

리뷰

수열의 중복을 허용하지 않고, 사전 순으로 증가하는 순서로 출력해야 한다.

수열은 오름차순이어야 하므로 go 함수에 start 변수를 넣어서 이전 인덱스 보다 큰 인덱스부터 수열의 숫자를 고르도록 했다.

코드

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

// n과 m  (6)
// 중복 허용 안 함. 오름차순 수열.

int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.  
int arr[10];
int ch[10];
int answer[10];

void go(int index, int start){

    if(index == M){
        for(int i = 0; i < M; i++){
            printf("%d ", answer[i]);
        }
        cout << '\n';
        return;
    }

    for(int i = start; i < N; i++){
        if(ch[i]) continue;

        ch[i] = 1;
        answer[index] = arr[i];
        go(index+1, i+1);
        ch[i] = 0;
    }
}

int main(void){

    cin >> N >> M;

     for(int i = 0; i < N; i++){
         scanf("%d", &arr[i]);
    }

    sort(arr, arr+N);

     go(0, 0);

    return 0;
}

문제

알고스팟 백준 1261번

리뷰

"맞았습니다!" 를 보고 나서야 후련했다.

자꾸 틀렸던 이유는 boundary_check 함수에서 x는 N보다 작고, y는 M보다 작은지 확인해야 하는데,

y도 N보다 작다고 코딩해서 계속 틀렸었다....

deque를 써서 벽을 부순 경우에는 push_back , 빈 방에 온 경우 벽은 안부숴도 되니까 push_front 로 해결했다.

방문 표시를 하는 배열을 써도 되고, 안써도 된다.

구글링을 해보면 다익스트라를 쓴 코드도 있었다.

그리고 배운 점은, 정수1개를 입력 받을 때는 1d를 쓴다는 것이다.

for(int i = 1; i <= N; i++){     //map 입력받기
    for(int j = 1; j <= M; j++){
        scanf("%1d", &map[i][j]);  // 정수 1개를 입력 받을 때는 1d 를 쓴다. 
        broken_cnt[i][j] = -1;  // 전부 -1로 초기화 
    }
} 

변수명, 함수명도 약어 없이 짓고 누구나 이해할 수 있도록 직관적이고 자세하게 적는게 좋다는데.

알고리즘 문제를 풀 때는 자꾸 짧게만 쓰게 된다. 마음이 급해서 그런가보다.

백준 문제 중에 BFS 가 필요한 숨바꼭질, 숨바꼭질3을 풀어본게 도움이 됬던 것 같다.

코드 1

main() 함수는 최대한 간결해야 한다는 글을 읽어서 Input 과 Solve 로 코드를 분리해 보았다.

#include <iostream>
#include <algorithm> 
#include <vector>
#include <deque>
#include <utility>
#define MAX 101
using namespace std;

int N, M, answer;  // 세로 N, 가로M

int map[MAX][MAX]; // 지도  
int broken_cnt[MAX][MAX] = {-1, }; // // 현재 지점에서 벽을 부순 횟수
bool visit[MAX][MAX]; // 방문 여부 

int xx[5] = {0, 0, -1, 1};
int yy[5] = {-1, 1, 0, 0};

deque<pair<int, int> > de;

bool check_boundary(int x, int y){
    return (x <= N && x >= 1 && y <= M && y >= 1 );
}

void BFS(int x, int y){ // (1,1)에서 시작해서 (N,M)에 도착해야 한다.  

    de.push_back( {x, y});
    broken_cnt[x][y] = 0;
    visit[x][y] = true;

    while(!de.empty()){  

        int now_x = de.front().first;
        int now_y = de.front().second;
        de.pop_front();

        for(int i=0; i < 4; i++){

            int next_x = now_x + xx[i];
            int next_y = now_y + yy[i];

            if(check_boundary(next_x, next_y) == false) continue; // 좌표 범위 체크  

            if(true == visit[next_x][next_y]) continue; // 이미 방문했다면 지나간다. 

            if(map[next_x][next_y] == 1){  // 벽이면 뚫는다.  
                broken_cnt[next_x][next_y] = broken_cnt[now_x][now_y]+1; 
                visit[next_x][next_y] = true;
                de.push_back({next_x, next_y});

            }else if(map[next_x][next_y] == 0){ // 빈방이면 안 뚫어도 된다. 
                broken_cnt[next_x][next_y] = broken_cnt[now_x][now_y];
                visit[next_x][next_y] = true;
                de.push_front({next_x, next_y});

            }
        }

    }
}

void Solve(){
    BFS(1, 1);
     cout << broken_cnt[N][M];
}

void Input(){
    cin >> M >> N ; // 가로M, 세로 N

    for(int i = 1; i <= N; i++){     //map 입력받기
        for(int j = 1; j <= M; j++){
            scanf("%1d", &map[i][j]);  // 1개의 정수를 입력받을 때 1d 
         }
    } 
}

int main(void){

    Input();

    Solve();   

    return 0;
} 

코드2

#include <iostream>
#include <algorithm> 
#include <vector>
#include <deque>
#include <utility>
#define MAX 101
using namespace std;


int N, M, answer;
int map[MAX][MAX]; // 지도  
int broken_cnt[MAX][MAX] = {-1, }; // // 현재 지점에서 벽을 부순 횟수

int xx[5] = {0, 0, -1, 1};
int yy[5] = {-1, 1, 0, 0};

deque<pair<int, int> > de;

bool check_boundary(int x, int y){ // 좌표 범위 체크  
    return (x <= N && x >= 1 && y <= M && y >= 1 );
}

void BFS(){ // (1,1)에서 시작해서 (N,M)에 도착해야 한다.  

    de.push_back( {1, 1});
    broken_cnt[1][1] = 0; // 일단 방문하면 0 

    while(!de.empty()){  

        int now_x = de.front().first ;
        int now_y = de.front().second;
        de.pop_front();

        int now_cnt = broken_cnt[now_x][now_y]; // 현재 지점에서 벽을 부순 횟수  

        for(int i=0; i < 4; i++){
            int next_x = now_x + xx[i];
            int next_y = now_y + yy[i];

            if(check_boundary(next_x, next_y) == false) continue; // 좌표 범위 체크  

            if(broken_cnt[next_x][next_y] != -1) continue; // 이미 방문했다면 지나간다. 

            if(map[next_x][next_y] == 1){  // 벽이면 뚫는다.  
                broken_cnt[next_x][next_y] = now_cnt+1; 
                de.push_back({next_x, next_y});

            }else if(map[next_x][next_y] == 0){ // 빈방이면 안뚫어도 된다  
                broken_cnt[next_x][next_y] = broken_cnt[now_x][now_y];
                de.push_front({next_x, next_y});
            }
        }

    }
}

void Solve(){

    BFS();
     cout << broken_cnt[N][M];
}

void Input(){

    cin >> M >> N ; // 가로M, 세로 N

    for(int i = 1; i <= N; i++){     //map 입력받기
        for(int j = 1; j <= M; j++){
            scanf("%1d", &map[i][j]);  // 정수 1개를 입력 받을 때는 1d 를 쓴다. 
            broken_cnt[i][j] = -1;  // 전부 -1로 초기화 
        }
    } 
}

int main(void){

    Input();

    Solve();   

    return 0;
} 

문제

부등호 백준 2529번

리뷰

부등호의 개수k와 부등호 리스트가 주어진다.

< < < > < < > < >

k+1 개의 숫자를 나열하여 부등호를 만족시켜야 한다. 0부터 9까지의 숫자만 사용 가능하다.

이를 만족하는 수열 예시 2개는 아래와 같다. 수열은 모두 달라야 한다. 숫자를 모두 이어붙이면 하나의 '숫자'가 된다.

//  3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 
3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0
5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

주어진 부등호 관계를 만족하는 k+1자리의 최소 정수와 최대 정수를 출력해야 한다.

0부터 9까지 10가지의 숫자를 중복하지 않고 수열을 만드는 것은 재귀를 이용하여 N과 M 시리즈 문제에서 해봤다.

아래는 기본 구조다. index는 채워야 할 자리의 index 이다.

만약 4자리 숫자로 구성된 수열을 만들어야 하면, (n == 4 라고 가정)

index가 0,1,2,3 까지 변화하면서 for문에서 숫자를 선택하여 채우고, ( 이 때, ch[i] 배열을 검사하면서 선택이 이미 된 )

index가 4가 된 순간에 if문 조건을 만족시키면서 수열이 완성되서 return 된다.

bool ch[11]; // 중복을 피하기 위한 체크 배열 

void Combination(int index){ 

    if(index == n ){ // 수열 완성. 
        //
        return;      
    }

    for(int i = 0; i <= 9; i++){
        if(ch[i]) continue; // 이미 사용한 숫자라면 지나감

         ch[i] = true; // 선택
         Combination(index+1); // 다음 자리수 선택을 위해 재귀 호출 
         ch[i] = false; // 선택 안함  
    } 
}

이 문제에서는 백트레킹 기법을 쓴다.

백트레킹은 의미 없는 함수 호출을 피하기 위해 앞에 조건문으로 검사해서 함수 호출 횟수를 줄이는 것이다.

k 개의 부등호가 주어지면, 수열의 숫자는 k+1개로 구성된다.

Combination 함수는 index 자리의 숫자를 선택하면서 숫자를 string num에 담아서 넘긴다.

만약 첫째 자리 숫자를 선택해야 하는 index == 0 인 상황에는, 무조건 숫자를 선택한다. 재귀 호출을 피할 이유가 없다.

이와 달리 index가 1 이상인 경우, 즉 둘째, 셋째 그 이상의 자리의 숫자를 선택해야 하는 상황일 때는 앞자리 숫자와 부등호를 고려해야 한다.

// 왜냐하면 첫째 숫자가 9 이고 부등호가 < 인 경우가 있다. 그런데 9 를 초과하는 1자리 숫자는 없다.

if(index == 0 || SignCheck(num[index-1], i+'0', sign[index-1]))

// 따라서 앞자리 숫자, 현재 선택하려는 숫자, 앞자리 부등호를 인자로 넘겨서 검사한다.
// 아래는 함수의 시그니처다.     
bool SignCheck(char a, char b, char oper); 

SignCheck 함수는 현재 선택하려는 숫자 b가 부등호를 만족시킬 수 있는 숫자라면 true를 반환한다.

수열이 완성되면 index가 k+1이 되는 순간이다. 그 때 ans 벡터에 넣는다.

답은 최대, 최소 숫자니까 ans 벡터를 정렬해서 맨앞, 맨뒤 값을 출력하면 된다.

void Combination(int index, string num){ 
    // index : 선택해야 할 (수열에서의) 숫자 자리. 0부터 9까지. 

    if(index == (k+1) ){ // 수열 완성. 벡터에 넣는다 
        ans.push_back(num); 
        return;      
    }

    for(int i = 0; i <= 9; i++){
        if(ch[i]) continue; // 이미 사용한 숫자라면 지나감

        // 첫번째 자리 숫자를 고르는 거라면, 무조건 선택. (index == 0)
        //  그게 아니라면, 앞자리 숫자 num[index-1] 과 현재 선택하려는 숫자 i 와 부등호를 넘긴다.  
        if(index == 0 || SignCheck(num[index-1], i+'0', sign[index-1])){
            ch[i] = true; // 선택
             Combination(index+1, num + to_string(i)); // 다음 자리수 선택을 위해 재귀 호출 
            ch[i] = false; // 선택 안함  
        }

    } 
}

코드

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


int k;
char sign[11];  // 부등호 담은 수열   
int num[11];     // 조합으로 만들어진 수열  
bool ch[11];  // 숫자 중복 불허 
vector<string> ans; // 부등호를 만족하는 수열을 저장하는 벡터 
string maxnum, minnum;

bool SignCheck(char a, char b, char oper){ // 부등호를 만족시키는지 검사

    if(oper == '<'){
        if(a>b) return false;

    } else {// '>'
        if(a<b) return false;
    }
    return true;
}

void Combination(int index, string num){ 
    // index : 선택해야 할 (수열에서의) 숫자 자리. 0부터 9까지. 

    if(index == (k+1) ){ // 수열 완성. 벡터에 넣는다 
        ans.push_back(num); 
        return;      
    }

    for(int i = 0; i <= 9; i++){
        if(ch[i]) continue; // 이미 사용한 숫자라면 지나감

        // 첫번째 자리 숫자를 고르는 거라면, 무조건 선택. (index == 0)
        //  그게 아니라면, 앞자리 숫자 num[index-1] 과 현재 선택하려는 숫자 i 와 부등호를 넘긴다.  
        if(index == 0 || SignCheck(num[index-1], i+'0', sign[index-1])){
            ch[i] = true; // 선택
             Combination(index+1, num + to_string(i)); // 다음 자리수 선택을 위해 재귀 호출 
            ch[i] = false; // 선택 안함  
        }
    } 
}


int main(void){

    cin >> k;

     for(int i = 0; i < k; i++){
         cin >> sign[i];
    } // 입력받기 끝 

    Combination(0, "");    

    sort(ans.begin(), ans.end()); // 오름차순 정렬 후, 맨 뒤가 최대, 맨 앞이 최소

    cout << ans[ans.size()-1] << '\n' << ans[0];

    return 0;
} 

문제

부분수열의 합 백준 1182번

리뷰

혼자 힘으로 못풀겠어서 다른 분들 코드를 봤다.

N개의 숫자를 입력받아서 합이 S가 되는 부분 집합의 개수를 구하는 문제다.

부분 집합을 만들 줄 알아야 한다.

인덱스 0부터 N-1 까지 순회하면서, 현재 인덱스의 숫자를 집합에 '포함' / '미포함' 을 구분하여 재귀호출한다.

탐색 함수의 시그니처는 현재 index를 나타내고, 공집합이면 안되니까 포함시킨 숫자의 cnt를 세준다.

void dfs(int index, int sum, int cnt)

코드

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


int N, S, answer;
int a[21];

void dfs(int index, int sum, int cnt){

    if(index == N){
        if(S == sum && cnt > 0) {
            answer++;
        }
        return;
    }

    dfs(index+1, sum+a[index], cnt+1); // 포함한다.
    dfs(index+1, sum, cnt); // 포함 안한다  
} 

int main(void){

    cin >> N >> S;

    for(int i = 0; i < N; i++){
        scanf("%d", &a[i]);
    } // 수열의 수를 입력받는다. 

    dfs(0, 0, 0);

    cout << answer;

    return 0;
} 

문제

외판원 순회2 백준 10971번

리뷰

N개의 도시가 있다. 어떤 도시에서 시작해서 모든 도시를 방문하고 다시 시작 도시로 돌아오는 최소 비용을 구하는 문제.

완전탐색으로 풀었다.

N개 도시를 모두 시작점 삼아서 탐색해봐야 한다.

for문 하나면 되는데, 이중 for문으로 해서 틀렸었다...

탐색 함수의 시그니처는 아래와 같다.

void search(int visit_city, int cnt, int cost);
// visit_city는 현재 도시 번호
// cnt는 그동안 방문 도시 개수
// cost는 이동하면서 누적한 비용

cnt가 N개가 되는 순간, 현재 지점에서 '시작점' 으로 갈 수 있는지 확인하고, 이동 후 최소비용을 갱신한다.

search 함수 내부에 재귀호출이 있는 for문이 있다.

i와 j간에 경로가 없는 경우 m 배열 값이 0이니까 continue 처리한다.

이미 방문한 도시도 재방문하면 안되니까 continue 처리한다.

void search(int visit_city, int cnt, int cost){

    if(cnt == N ){ // 모든 도시 방문했고, 목적지 도착시 종료   
        if(m[visit_city][start_city] > 0){ // 시작점으로 돌아옴. 
            mcost = min(cost + m[visit_city][start_city], mcost);
        }
        return; 
    }

    for(int a = 0; a < N; a++){ 

        if(m[visit_city][a] == 0) continue; // 못가는 곳  
        if(visit_check[a] == true) continue; // 이미 방문한 도시 

        visit_check[a] = true; // 방문표시  
        search(a, cnt+1, cost + m[visit_city][a]); // 방문해본다  
        visit_check[a] = false; 
    }
}

코드1

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

// 외판원순회2

int N;
int m[11][11];
int visit_check[11]; // 방문체크 
int mcost = 2e9;  // 최소비용 
int start_city; // 시작지점이자 목적지점

void search(int visit_city, int cnt, int cost){

    if(cnt == N ){ // 모든 도시 방문했고, 목적지 도착시 종료   
        if(m[visit_city][start_city] > 0){ // 시작점으로 돌아옴. 
            mcost = min(cost + m[visit_city][start_city], mcost);
        }
        return; 
    }

    for(int a = 0; a < N; a++){

        if(m[visit_city][a] == 0) continue; // 못가는 곳  
        if(visit_check[a] == true) continue; // 이미 방문한 도시 

        visit_check[a] = true; // 방문표시  
        search(a, cnt+1, cost + m[visit_city][a]); // 방문해본다  
        visit_check[a] = false; 
    }
}


int main(void){

    cin >> N; // 도시 개수 

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> m[i][j];
        }    
    } // 입력받기 끝. 

    for(int i = 0; i < N; i++){

        start_city = i; // 시작 도시 번호 
        visit_check[i] = true; // 시작 도시 방문했으니까 cnt 1 로 시작 
        search(i, 1, 0); 
        visit_check[i] = false;
    }

    cout << mcost;

    return 0;
} 

코드2

next_permutation() 써서 풀 수 있다. 왜냐하면, 어떤 순서대로 도시를 방문해야 하는가 의 문제이기 때문에.

순열을 리턴해주는 함수로 해결가능하다.

도시 번호 수열을 만들기 위해 A [ ] 배열을 만든다. 1 2 3 ... N 의 숫자가 들어간다.

마지막 N번 도시에서 1번 도시로 (시작점으로) 오는 경로가 있는 경우 비용을 합산한다.

next_permu() 함수가 만들어주는 수열 대로 방문한다.

경로가 없으면 모든 도시를 방문할 수 없기 때문에 all_visit 플래그를 활용한다.

모든 경로를 방문한 경우에만 최소비용을 갱신한다.

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

// 외판원 순회2 

int N;
int M[11][11];
int A[11]; // 도시 번호 


int main(void){

     freopen("input.txt", "rt", stdin);

    cin >> N;

    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> M[i][j];
        }
    } // 도시 간의 경로 입력받기 끝. 


    for(int i = 1; i <= N; i++){ // 도시에 번호 붙이기 (1부터 N까지) 
        A[i] = i;
    }

    int mincost = 2e9;

    do{
        int cost = 0;
        bool all_visit = true;
        int i = 1;

        for(i = 1; i <= N-1; i++){

            if(M[A[i]][A[i+1]] > 0){
                cost += M[A[i]][A[i+1]];
            }else{
                all_visit = false; // 경로가 없어서 실패.
                break;
            }
        }

        // 마지막 N번 도시에서 1번 도시로 (시작점으로) 오는 경로가 있는 경우 비용을 합산.
        if(M[A[N]][A[1]] > 0) cost += M[A[N]][A[1]];
        else all_visit = false; // 모든 도시 방문 실패.  

        if(all_visit){
            mincost = min(cost, mincost);
        }

    }while( next_permutation(A, A+N));

    cout << mincost;

    return 0;
}