전체탐색법(Brute force)

전체탐색법

전체탐색법은 모든 문제해결의 기초가 되는 가장 중요한 설계법 중 하나라고 할 수 있다. 주어진 문제에서 해가 될 수 있는 모든 가능성을 검사하여 해를 구하기 때문에 항상 정확한 해를 구할 수 있다는 점이 장점이다. 하지만 탐색해야할 내용이 너무 많으면 문제에서 제시한 시간 이내에 해결할 수 없다는 점을 유의해야 한다.

하지만 전체탐색을 기반으로 한 다양한 응용들이 있으며, 이러한 응용들을 통하여 탐색 해야할 공간을 배제해 나가면서 시간을 줄일 수 있는 다양한 방법들이 존재하기 때문에 잘 응용하면 많은 문제를 해결할 수 있는 강력한 도구가 될 수 있다. 따라서 전체탐색법을 잘 익혀두면 다른 알고리즘 설계법을 학습하는데 많은 도움이 된다.

전체탐색법은 선형구조의 탐색, 비선형구조의 탐색을 기반으로 하여 문제를 해결한다.

선형구조와 비선형구조의 전체탐색

선형구조의 전체탐색은 반복문을 이용하여 접근할 수 있다.
1차 원 뿐만 아니라 2차원 이상의 다차원 구조에 대해서도 선형구조로 탐색할 수 있다.

비선형구조의 전체탐색은 문제해결의 가장 기본이 되는 알고리즘 설계법인 백트래킹을 이용한다.
백트래킹 기법은 재귀함수를 이용하여 간단하게 구현할 수 있고, 다양한 문제를 해결하는데 많이 응용되는 방법이므로 반드시 익혀둘 필요가 있다.

주어진 문제들을 통하여 선형구조, 비선형구조의 전체탐색법을 익힐 수 있도록 하자.

선형 구조에서의 전체탐색

약수의 합

한 정수 n을 입력받아서 n의 모든 약수의 합을 구하는 프로그램을 작성하시오.

예를 들어 10의 약수는 1, 2, 5, 10이므로 이 값들의 합인 18이 10의 약수의 합이 된다.

입력
첫 번째 줄에 정수 n이 입력된다. (단, 1 <= n <= 100,000)

출력
n의 약수의 합을 출력한다.
-------------------
입력 예
10

출력 예
18

이 문제는 기본적으로 수학적인 아이디어를 이용하여 해결할 수 있는 문제이지만 이 단 원에서는 전체탐색법을 다루는 단원이므로 전체탐색법으로 해결해보자.

일단 n을 입력받으면 1부터 n까지의 모든 수를 차례로 반복문을 이용하여 선형으로 탐색하면서 n의 약수들을 검사한다. 만약 현재 탐색 중인 수가 n의 약수라면 누적하여 구할 수 있다. 이렇게 구한다면 계산량은 O(n)이 된다. 이 문제에서는 n의 최댓값이 100,000이므로 충분히 해결할 수 있는 문제가 된다.

어떤 수 x가 n의 약수라면 다음 조건을 이용해 구할 수 있다.

n % x == 0

이를 이용하여 문제를 해결한 소스코드는 다음과 같다.

#include <stdio.h>
int n;
int solve() {
    int ans=0;
    for(int i=1; i<=n; i++ )
        if(n%i==0)
            ans+=i;
    return ans;
}

int main() {
    scanf("%d", &n);
    printf("%d\n", solve());
}

이문제는 이와 같은 방법으로 쉽게 해결할 수 있으나, n이 10억 이상의 값으로 커질 때는 다른 방법을 생각해야 한다.
아마 다른 포스트에서 다루게 될 것이므로 한 번 생각해보자.

최댓값

다음과 같이 9×9 격자판에 쓰여진 81개의 자연수가 주어질 때, 이들 중 최댓 값을 찾고
그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.

예를 들어, 다음과 같이 81개의 수가 주어질 경우에는 이들 중 최댓값은 90이고, 이 값은 5행 7열에 위치한다.

  열 1  2  3  4  5  6  7  8  9
행
1    3 23 85 34 17 74 25 52 65
2   10  7 39 42 88 52 14 72 63
3   87 42 18 78 53 45 18 84 53
4   34 28 64 85 12 16 75 36 55
5   21 77 45 35 28 75 90 76  1
6   25 87 65 15 28 11 37 28 74
7   65 27 75 41  7 89 78 64 39
8   47 47 70 45 23 65  3 41 44
9   87 13 82 38 31 12 29 29 80

입력
첫째 줄부터 아홉째 줄까지 한 줄에 아홉 개씩 자연수가 주어진다. 주어지는 자연 수는 100보다 작다.

출력
첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 위치한 행 번호와 열 번호를 빈칸을 사이에 두고 차례로 출력한다.
최댓값이 두 개 이상인 경우 그 중 한 곳의 위치를 출력한다.
----------------------------
입력 예
3 23 85 34 17 74 25 52 65
10 7 39 42 88 52 14 72 63
87 42 18 78 53 45 18 84 53
34 28 64 85 12 16 75 36 55
21 77 45 35 28 75 90 76 1
25 87 65 15 28 11 37 28 74
65 27 75 41 7 89 78 64 39
47 47 70 45 23 65 3 41 44
87 13 82 38 31 12 29 29 80

출력 예
90 57

이 문제는 2차원 구조를 선형으로 모두 탐색하면 쉽게 해결할 수 있는 문제이다.
2차원 구조는 행 우선으로 탐색하는 방법과 열 우선으로 탐색하는 방법이 있는데, 이 문제는 어떤 방법으로 탐색해도 관계없으며, 일반적으로는 행 우선 탐색을 많이 사용한다.

다음은 행 우선을 반복문으로 구현한 소스코드이다.

for(int row=0; row<5; row++) {
    for(int col=0; col<4; col++)
        printf("[%d, %d]", row, col);
    uts("");
}

이제 문제를 해결하는 방법에 대해서 알아보자.

탐색하기 전 먼저 해를 저장할 변수인 ans를 0으로 초기화한다. 여기서 주의할 점은 각 원소들 중 음수값이 존재할 경우 최댓값을 구하기 위해 ans를 0으로 초기화하면 안 된다는 점이다. 이 문제는 음수값이 존재하지 않기 때문에 ans를 0으로 초기화하고 문제를 해결한다.

참고로 어떤 변수에 값을 초기화하는 몇 가지 방법을 소개한다. 일단 int형의 최댓값은 0x7fffffff(2,147,483,647)이며, 최솟값은 0x80000000(-2,147,483,648)이다. 엄밀하게 최대, 최소를 지정할 때 이 값을 이용하면 되며, 16진법을 이용하면 쉽게 처리할 수 있다.

여기서 주의할 점은 위 값들을 설정한 후 값을 증가시키거나 감소시키면 오버플로 (overflow)로 인하여 답이 잘못될 수 있다.
예를 들어 다음 명령을 보자.

int max = 0x7fffffff;
max=max+1;

위 예의 경우에 max값이 최댓값이었는데, 여기서 1을 증가하면 오버플로가 발생하 여 max값은 음수가 된다.
따라서 이런 점을 방지하기 위하여 적어도 2배 정도라 하더 라도 오버플로가 발생하지 않도록 처리하는 경우가 많다.
이럴 때는 주로 최댓값을 987654321 등의 자릿수도 쉽게 알 수 있고 2배를 하더라도 정수 범위에 있는 수 등을 활용하는 경우가 많다. 문제에 따라서는 탐색하고자 하는 데이터 중에서 임의의 한 값 을 최댓값 또는 최솟값으로 결정하는 방법도 있다.

위 문제를 해결하는 소스코드는 다음과 같다.

#include <stdio.h>
int A[10][10], ans, mi, mj;
void input() {
    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
        scanf("%d", &A[i][j]);
}
int solve() {
    for(int i=0; i<9; i++)
        for(int j=0; j<9 ; j++)
            if(ans < A[i][j]) {
                ans=A[i][j];
                mi=i+1; mj=j+1;
            }
}
int main() {
    input();
    solve();
    printf("%d\n%d %d\n", ans, mi, mj);
    return 0;
}

가장 일반적으로 해결할 수 있는 방법이고 이 경우 계산량은 O(row x column)이 된다.
이를 보다 효율적으로 바꾸기 위해서, 입력받으면서 바로 처리할 수도 있으며, ans, mi, mj를 모 두 쓰지 않고 mi, mj만 가지고 처리하는 방법을 소개한다.

#include <stdio.h>
int A[10][10], mi, mj;
void input_solve() {
    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++) {
            scanf("%d", &A[i][j]);
            if(A[mi][mj]<A[i][j])
                mi=i, mj=j;
        }
}
int main() {
    printf("%d\n%d %d\n", A[mi][mj], mi+1, mj+1);
    return 0;
}

고기잡이

우리나라 최고의 어부 정올이가 이번에 네모네모 배 고기잡이 대회에 참가한다.

이 대회에는 3개의 라운드가 있는데, 첫 번째 라운드는 1차원 형태로 표현될 수 있는 작은 연못에서
길쭉한 그물을 던져서 최대한 많은 고기를 잡는 것이 목적이다.

1라운드의 예를 들면 연못의 크기가 1*6이고 물고기의 위치와 가치가 다음과 같다고 하자.

1 0 2 0 4 3

여기서 그물의 크기는 1*3이라고 할 때, 잡을 수 있는 방법은
(1 0 2), (0 2 0), (2 0 4), (0 4 3)의 4가지 방법이 있다.

이 중 가장 이득을 보는 방법은 마지막 방법 0 + 4 + 3 = 7이다.
따라서 주어진 경우의 최대 이득은 7이 된다.
정올이는 최대한 가치가 큰 물고기를 잡아서 우승하고 싶어 한다.

연못의 폭과 각 칸에 있는 물고기의 가치, 그물의 가로의 길이와 세로의 길이가 주어질 때,
잡을 수 있는 물고기의 최대이득을 구하는 프로그램을 작성하시오.

입력
첫 번째 줄에 연못의 폭 N이 입력된다. ( N <= 100 인 자연수 )
두 번째 줄에 그물의 폭 W가 입력된다. ( W <= N 인 자연수 )
세 번째 줄 W개의 물고기의 가치가 공백으로 구분되어 주어진다. 각 물고기의 가
치는 7이하의 자연수이다. 0일 경우에는 물고기가 없다는 의미이다.

출력
잡을 수 있는 물고기의 최대 가치를 출력한다.
---------------------------------
입력 예
6
3
1 0 2 0 4 3

출력 예
7

이 문제는 전체탐색법을 이용하여 간단하게 해결할 수 있다.
폭이 n인 연못에서 폭이 w인 그물을 던졌을 때 최대 이득을 얻을 수 있는 구간을 찾는 문제이다.
가장 단순한 방 법으로 n개의 주어진 수들 중 연속된 w개의 수들을 탐색하여 합을 구한 다음 최댓값을 갱신하는 방법으로 접근할 수 있다.
먼저 첫 번째 데이터부터 탐색하여 w개의 합을 구한 다음 최댓값을 갱신하고, 두 번째 데이터부터 탐색하여 w개의 합을 구하여 최댓값을 갱신한다. 이런 방법으로 모든 구간을 전체탐색법으로 확인할 수 있다.

입출력 예의 경우 다음과 같은 과정으로 해를 구해나간다.

위의 과정을 보면 탐색을 시작하는 지점이 0번으로부터 시작하여 1씩 증가하는 것을 알 수 있으며, 시작점을 지정하면 그물의 폭인 w만큼 탐색을 진행한다. 따라서 마지막 탐색 의 시작 지점은 n - w + 1 이 된다. 핵심 탐색 부분을 구현하면 다음과 같다.

for(int i=0; i<N‐W+1; i++) {
    for(int j=0; j<W; j++)
        printf("%d ", i+j);
    puts("");
}

n = 8 이고 w = 5 일 때, 위 탐색방법의 출력결과는 결과는 다음과 같다.

0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7

즉, [0, 4] 구간, [1, 5]구간, [2, 6]구간, [3, 7]구간으로 모두 4번을 검사한다.

위 소스코드에서 n - w + 1 을 생각하기 어려운 경우에는 배열을 좀 더 크게 잡은 후 다음과 같이 작성해도 관계없다.

for(int i=0; i<N; i++) {
    for(int j=0; j<W; j++)
        printf("%d ", i+j);
    puts("");
}

위와 같이 작성하면 생각하기 쉽기 때문에 빠른 시간에 코딩이 가능하다. 위의 코드의 출력결과는 다음과 같다.

0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9
6 7 8 9 10
7 8 9 10 11

위의 아이디어 들을 이용하여 문제를 해결한 소스코드는 다음과 같다.

#include <stdio.h>
int data[101], N, W, ans = 0;
int main() {
    scanf("%d%d", &N, &W);
    for(int i=0; i<N; i++)
        scanf("%d", data+i);

    for(int i=0; i<N+W‐1; i++) {
        int sum=0;
        for(int j=0; j<W; j++)
            sum+=data[i+j];
        if(sum>ans) ans=sum;
    }
    printf("%d", ans);
}

이 알고리즘의 계산량은 1~N의 각 위치에 대해서 W만큼 탐색을 하므로 O(NW)가 됨 을 알 수 있다.
문제에서 제시한 N의 최대치가 100,000이 입력되고 그물의 크기가 적당히 크면 수행시 간이 많이 걸리므로 좀 더 효율적인 알고리즘이 필요하다.

비선형 구조에서의 전체탐색

계단 오르기

길동이는 n개의 단으로 구성된 계단을 오르려고 한다.
길동이는 계단을 오를 때 기분에 따라서 한 번에 1단 또는 2단을 올라갈 수 있다.
계단의 크기 n이 주어질 때, 길동이가 이 계단을 올라갈 수 있는 모든 경우의 수를
구하는 프로그램을 작성하시오.

만약 계단이 3개라면 길동이는 1, 1, 1로 올라가는 법과 1, 2로 올라가는 법, 2, 1로
올라가는 법의 3가지 서로 다른 방법이 있다.
-----------------------------------------
입력
계단의 수 n이 입력된다(단 n은 20보다 작은 자연수).

출력
길동이가 계단을 오르는 모든 방법의 수를 출력한다.

입력 예         출력 예
3              3

이 문제도 비선형구조로 전체탐색을 하여 해를 구할 수 있다.
현재 상태에서 1칸 또는 2 칸을 올라갈 수 있으므로, 탐색구조를 다음과 같이 설정할 수 있다.

단, 주의할 점은 정확 하게 n칸에 도착했을 때만 한 가지 경우로 처리해야한다는 점이다.
예를 들어 도착점까지 한 칸 남았을 경우에는 2칸을 올라갈 수 없다.

위의 탐색 과정으로 5칸의 계단을 오르는 과정을 보면 다음과 같다.

위와 같은 트리를 구성하면서 전체탐색을 하면 n은 5일 때, 방법은 8임을 알 수 있다.
이와 같은 구조의 탐색을 소스코드로 구현하면 다음과 같다.

#include <stdio.h>
int n, ans;
void solve(int v) {
    if(v>n) return; // --- (a)
    if(v==n){ // 현재 n칸이면
        ans++;
        return;
    }
    solve(v+1); // 1칸 오르기
    solve(v+2); // 2칸 오르기
}
int main() {
    scanf("%d", &n);
    solve(0);
    printf("%d\n", ans);
}

Warning: (a)행의 조건은 마지막 계단을 넘어가는 경우를 처리한다. 이 구문이 없으면 무한 재귀에 빠지게 된다.

거스름 돈

여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는 자동판매기용 프로그램의
개발을 의뢰받았다. 거스름돈에 사용될 동전의 수를 최소화하는 것이다.

입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가짓수
그리고 동전의 종류가 들어오면 여러 가지 방법들 중 가장 적은 동전의 수를 구하는
프로그램을 작성하시오.

-----------------------------------------
입력
첫 번째 줄에는 거슬러 줘야할 돈의 액수 m이 입력된다.
( 10 <= m <= 10,000 )
다음 줄에는 그 나라에서 사용되는 동전의 종류의 수 n이 입력된다.
( 1 <= n <= 10 )
마지막 줄에는 동전의 수만큼의 동전 액수가 오름차순으로 입력된다.
( 10 <= 액수 <= m )

출력
최소의 동전의 수를 출력한다.

입력 예
730
5
10 50 100 500 1250

출력 예
6

이 문제는 매우 잘 알려진 유명한 문제 중 하나로 다양한 방법으로 해결할 수 있는 대표적인 문제이다. 이 단원에서는 전체탐색법을 기반으로 하여 해결하는 방법에 대해서 소개한다. 대부분의 문제들에서도 마찬가지지만 문제를 전체탐색으로 구조화하는 방법에 따라 해법의 계산량이 달라질 수 있다.

이 문제에서는 2가지 서로 다른 구조화로 해결하는 방법을 소개한다. 먼저 첫 번째 방법은 문제의 상태를 지금까지 지불한 액수로 설정하고, 서로 다른 동전 1개를 이용하여 지불하는 경우를 간선으로 생각할 수 있다.

이 방법으로 구조화하는 방법은 다음 그림과 같다. 이 때 $x$의 값은 지금까지 지불한 액수이며 사용 가능한 동전은 4가지 종류로 10원, 50원, 100원, 500원일 때를 가정한 것이다.

처음에 0원으로 출발하여 각 동전을 지불해 나가며, 지불할 금액과 일치할 때의 깊이가 지불한 동전의 개수이므로, 지불할 금액과 일치하는 최소 깊이를 구하는 문제가 된다. 만약 지불할 금액과 일치했거나 금액을 초과했을 경우에는 백트랙하면서 탐색을 진행하도록 코드를 작성하면 된다.

지불해야할 금액이 120원이고, 사용가능한 동전이 30원, 50원, 60원, 100원일 때의 전체 탐색구조는 다음과 같다. 먼저 처음 깊이 1까지의 구조이다.

다음은 30원 이하의 정점들의 전체적인 구조이다. 파란색 정점은 120원 지불에 성공한 것을 나타낸다.

계속해서 50원과 60원 정점의 전체 탐색구조를 나타낸다. 100원 이하에서는 더 이상의 탐색이 불가능하다.

#include<stdio.h>
int m, n, coin[10], ans=987654321;
void solve(int mon, int d) {
    if(mon>m) return;
    if(mon==m){
        if(d<ans) ans=d;
        return;
    }
    for(int i=0; i<n; i++)
        solve( mon+coin[i], d+1 );
}
int main() {
    scanf("%d %d", &m, &n);
    for(int i=0; i<n ; i++ )
        scanf("%d", coin+i);
    solve(0, 0);
    printf("%d\n", ans);
    return 0;
}

위 프로그램에서의 solve()함수는 다음과 같은 상태를 표현하고 있다.

solve(mon, d) = “d개의 동전으로 mon원을 사용한 상태”

이 방법은 정확하게 해를 구할 수는 있으나 이론상으로 최대 금액이 10,000원이고 최소 액수가 10원이므로 최대 깊이가 1,000까지 갈 수 있기 때문에 시간 내에 해결할 수 없다.

시간을 줄이기 위한 다양한 방법이 있지만, 이번에는 다른 구조를 이용하여 해결할 수 있는 방법을 소개한다. 탐색구조를 어떻게 설계하느냐에 따라서 해법의 계산량이 달라질 수 있다는 것을 알고, 문제를 해결할 때, 탐색구조를 어떻게 구성해야하는지 먼저 고민하는 것이 중요하다.

이번에 소개하는 구조는 이전과는 달리 같은 깊이에서는 같은 동전으로만 지불하는 방법으로 구조를 구성한다. 한 깊이에서 간선의 수는 해당 깊이의 동전을 0개로부터 해당 금액을 최대한 지불할 수 있는 최대한의 수로 설정하여 진행한다. 다음 그림을 통하여 자세히 알아보자. 동전은 30원, 50원, 60원, 100원이다.

실제 지불할 금액은 120원, 지불가능한 동전의 수는 50원, 60원, 100원일 때의 경우 전체 구조는 다음과 같다.

이 방법으로 구현한 소스코드는 다음과 같다.

#include <stdio.h>
int n, m, coin[10], ans=987654321;
void solve(int mon, int k, int cnt) {
    if(mon==m){
        if(ans>cnt) ans=cnt;
        return; // 백트랙
    }
    if(k==n) return; // 더 이상 깊이 진행 X, 백트랙
    for(int i=0; mon+coin[k]*i<=m; i++) // 조건 만족하지 않을 시 백트랙
        solve(mon+coin[k]*i, k+1, cnt+i);
}
int main() {
    scanf("%d %d", &m, &n);
    for(int i=0; i<n; i++)
        scanf("%d", coin+i);
    solve(0, 0, 0);
    printf("%d\n", ans);
    return 0;
}

위 프로그램에서의 solve()함수는 다음과 같은 상태를 표현하고 있다.

solve(mon, k, cnt )= “k번째 이하의 동전을 cnt개 사용하여 mon원을 거슬러 준 상태”

이 방법은 앞에서 시도했던 방법보다 속도가 획기적으로 빨라진다. 그 이유는 전체 상태를 그려보면 앞의 방법보다 이번에 구조화한 방법의 정점의 수가 훨씬 적기 때문이다. 이와 같이 구조를 어떻게 설계하느냐에 따라 알고리즘의 계산량이 달라지기 때문에, 문제를 해결할 때 먼저 최적의 구조를 설계하는 것이 중요하다.

연구활동 가는 길

*위의 그래프를 참고하여 문제를 풀어보자*

정올이는 GSHS에서 연구활동 교수님을 뵈러 A대학교를 가려고 한다.
출발점과 도착점을 포함하여 경유하는 지역 n개, 한 지역에서 다른 지역으로 가는 방법이 총 m 개이며
GSHS는 지역 1이고 A대학교는 지역 n이라고 할 때 대학까지 최소 비용을 구하시오.

단, n은 10 이하, m은 30 이하, 그리고 한 지역에서 다른 지역으로
가는 데에 필요한 비용은 모두 200 이하 양의 정수이며
한 지역에서 다른 지역으로 가는 어떠한 방법이 존재하면
같은 방법과 비용을 통해 역방향으로 갈 수 있다.

위의 그래프는 예를 보여준다.
(단, 정점 a -> 정점 b로의 간선이 여러 개 있을 수 있으 며, 자기 자신으로 가는 정점을 가질 수도 있다.)

최소 비용이 드는 경로 : 1→3→5→7, 최소 비용 : 69+59+21=149

입력
첫 번째 줄에는 정점의 수 n과 간선의 수 m이 공백으로 구분되어 입력된다.
다음 줄부터 m개의 줄에 걸쳐서 두 정점의 번호와 가중치가 입력된다. (자기 간선, 멀티 간선이 있을 수 있다.)

출력
대학까지 가는 데 드는 최소 비용을 출력한다. 만약 갈 수 없다면 “-1”을 출력.

----------------------------
입력 예
7 11
1 2 47
1 3 69
2 4 57
2 5 124
3 4 37
3 5 59
3 6 86
4 6 27
4 7 94
5 7 21
6 7 40

출력 예
149

이 문제는 그래프 상의 최단경로를 구하는 매우 유명한 문제이다.
이 문제를 해결하는 알고리즘은 여러가지가 알려져 있지만, 어려운 알고리즘을 모르더라도 전체탐색법을 통하여 해결할 수 있다.

이 문제는 그래프 구조이므로 비선형탐색법으로 해를 구할 수 있다.
먼저 출발정점에서 깊이우선탐색을 이용하여 출발점으로부터 도착점까지 가능한 모든 경로에 대해서 구해본다.

하나의 경로를 구할 때마다 해를 갱신하면서 최종적으로 가장 적합한 해를 출력한다.
주어진 예를 통하여 전체탐색하는 과정을 간단하게 살펴보자.

Warning: 중간에 몇개의 과정이 생략되었음에 유의

따라서 위의 경우 전체탐색법으로 탐색한 결과 최소 이동거리는 149가 됨을 알 수 있다.
위의 과정과 같은 방법으로 코딩한 결과는 다음과 같다.

#include<stdio.h>
int n, m, G[11][11], sol = 0x7fffffff, chk[11];
void solve(int V, int W) {
    if(V==n){ // 도착 여부를 확인하여 현재 정점이 도착점이라면
        if(W<sol) sol=W; // 더 좋은 해가 있으면 해를 갱신
            return; // 백트랙
    }
    for(int i=1; i<=n; i++)
        if(!chk[i] && G[V][i]) {
            chk[i]=1; // 다음 정점으로 진행할 때 다음 방문할 정점을 체크
            solve(i, W+G[V][i]); // 다음 정점으로 진행
            chk[i]=0; // 백트랙해서 돌아오면 체크를 해제
        }
}

int main(void) {
    scanf("%d %d", &n, &m);
    for(int i=0; i<m; i++) {
        int s,e,w;
        scanf("%d %d %d", &s, &e, &w);
        G[s][e]=G[e][s]=w;
    }
    solve(1, 0);
    printf("%d\n", sol==0x7fffffff ? ‐1:sol);
    return 0;
}

이 문제의 경우 정점과 간선의 수가 많지 않으므로 인접행렬로도 충분히 처리가 가능하기 때문에 인접행렬로 처리한다.
solve(a, b)는 현재 a정점까지 방문한 상태로 이동거리가 b라고 정의하고 있으며, chk배 열이 현재까지 방문한 정점들의 정보를 가지고 있다.
다음 정점으로 진행할 때 chk[i]=1 같이 chk배열에 다음 방문할 정점을 체크하고 만약 백트랙해서 돌아온다면, chk[i]=0 같이 체크를 해제하며 전체탐색을 진행한다.

if(V==n) 부분에서 도착 여부를 확인하여 현재 정점이 도착점이라면, 지금까지의 이동 거리와 현재 까지 구한 해를 비교하여 더 좋은 해가 있으면 해를 갱신한다. 이와 같이 작성할 경우 도시의 수가 n개라고 할 때 O(n!)의 계산이 필요하다.

다른 포스트에서 탐색배제를 이용하여 계산복잡도를 향상해본다.

References

• 문제해결을 위한 창의적 알고리즘