[백준][10971번] 외판원 순회 2

문제 URL

https://www.acmicpc.net/problem/10971

나의 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[][] w = new int[n][n]; // cost[i][j] - i에서 j까지 가는데 발생하는 비용
        int[] visit = new int[n]; // 도시를 방문해야하는 순서
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                w[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //초기화
        for (int i = 0; i < n; i++) {
            visit[i] = i;
        }

        int answer = Integer.MAX_VALUE;
        do {
            boolean ok = true;
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {
                int cost = w[visit[i]][visit[i + 1]];
                if (cost == 0) {
                    ok = false;
                    break;
                } else {
                    sum += cost;
                }
            }
            if (ok && w[visit[n - 1]][visit[0]] != 0) {
                sum += w[visit[n - 1]][visit[0]];
                if (sum < answer) {
                    answer = sum;
                }
            }
        } while (next_permutation(visit));

        System.out.println(answer);
    }

    public static boolean next_permutation(int[] a) {
        int i = a.length - 1;
        while (i > 0 && a[i - 1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length - 1;
        while (a[j] <= a[i - 1]) {
            j -= 1;
        }

        int temp = a[i - 1];
        a[i - 1] = a[j];
        a[j] = temp;

        j = a.length - 1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
}

다른풀이(C++)(1고정) **

시작점을 1로 고정한 풀이다. (중요!!!!)

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int a[20][20];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i][j]);
        }
    }

    vector<int> d(n);
    for (int i=0; i<n; i++) {
        d[i] = i;
    }

    int ans=2147483647;

    do {
        bool ok = true;
        int sum = 0;
        for (int i=0; i<n-1; i++) {
            if (a[d[i]][d[i+1]] == 0) {
                ok = false;
            } else {
                sum += a[d[i]][d[i+1]];
            }
        }
        if (ok && a[d[n-1]][d[0]] != 0) {
            sum += a[d[n-1]][d[0]];
            if (ans > sum) ans = sum;
        }
        //d.begin()+1 하는 부분이 다르다.(1 고정)
    } while (next_permutation(d.begin()+1, d.end()));

    printf("%d\n",ans);
    return 0;
}

다른 풀이**

시작점을 1로 고정한 풀이다. (중요!!!!)

import java.util.*;

public class Main {
    public static boolean next_permutation(int[] a) {
        int i = a.length-1;
        while (i > 0 && a[i-1] >= a[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }

        int j = a.length-1;
        while (a[j] <= a[i-1]) {
            j -= 1;
        }

        int temp = a[i-1];
        a[i-1] = a[j];
        a[j] = temp;

        j = a.length-1;
        while (i < j) {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int[] d = new int[n];
        for (int i=0; i<n; i++) {
            d[i] = i;
        }
        int ans = Integer.MAX_VALUE;

        do {
          //이부분이 달라짐 !
          // d[0] 1부분을 고정하기 위한 부분
            if (d[0] != 0) break;
            boolean ok = true;
            int sum = 0;
            for (int i=0; i<n-1; i++) {
                if (a[d[i]][d[i+1]] == 0) {
                    ok = false;
                } else {
                    sum += a[d[i]][d[i+1]];
                }
            }
            if (ok && a[d[n-1]][d[0]] != 0) {
                sum += a[d[n-1]][d[0]];
                if (ans > sum) {
                    ans = sum;
                }
            }
        } while(next_permutation(d));

        System.out.println(ans);
    }
}

느낀점

‘한 도시에서 시작해서 N개의 모든도시를 거쳐 다시 원래 도시로 돌아오려고 한다. (한번 갔던 도시로는 다시 갈 수 없다.)’

라는 두가지 힌트로 순열을 이용하는 문제 라고 유추해볼 수 있다.

또한 순열은 O(N*N!)이라는 많은 비용이 들기때문에 문제의 크기를 따져봐야한다.

문제의 크기 : 2<=N<=10 이므로 모든 경우를 다해봐도 된다!

• 중요!!! 모든 순서를 만들필요없다. 왜냐하면, 1,2,3,4 2,3,4,1 3,4,1,2 4,1,2,3 위 4가지 경우는 모두 같은 경우이다. 다시 시작한 도시로 돌아가야 하기떄문이다. 따라서 시작점을 1로 고정해도된다.

–> 시간복잡도 O(N!)으로 단축가능