[Java] 10971번: 외판원 순회 2

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

10971번: 외판원 순회 2

---

💡 접근 방법

1. 문제 이해

첫째 줄에 도시의 개수 N이 주어진다. 그리고 N개의 도시를 모두 방문하는 최소의 비용을 구하는 문제다.

예를 들어 1->2->3->4->1 이렇게 방문가능하다. 여기서 포인트가 있다.

1. 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획
   • N = 4 일경우 1번 도시를 시작해서 순회하고, 그다음 2번 도시를 시작,... 마지막 4번 도시를 시작
2. 단, 한 번 갔던 도시로는 다시 갈 수 없다.
   • 1->2->1->3->4->1 불가능
   • 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외

4
1: 0 10 15 20
2: 5  0  9 10
3: 6 13  0 12
4: 8  8  9  0

return 35

 

 

도시 1 → 도시 2 → 도시 4 → 도시 3 → 도시 1 이동 비용:

10(도시 1에서 2로) + 10(도시 2에서 4로) + 9(도시 4에서 3으로) + 6(도시 3에서 1로) = 35

 

 

2. 문제 풀이

• 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획
  • for 반목문을 사용해 시작 도시를 설정하고 isVisited를 초기화를 해준다.

for (int i = 0; i < N; i++) {
    isVisited = new boolean[N];
    isVisited[i] = true;
    backtracking(i, i, 0, 0);
    
    // backtracking(int start, int now, int depth, int cost)
}

• 단, 한 번 갔던 도시로는 다시 갈 수 없다.
  • isVisited 라는 boolean []을 만들어서 방문체크를 하고 backtracking에 적용할 계획이다.

for (int i = 0; i < N; i++) {
    if (!isVisited[i] && arr[now][i] != 0) {
        isVisited[i] = true;
        backtracking(start, i, depth + 1, cost + arr[now][i]);
        isVisited[i] = false;
    }
}

 

시작 도시를 포함하여 N개의 도시를 모두 방문했을 때의 값 depth가 N-1 이기 때문에 탈출조건으로 설정해 줬다. 하지만 여기서 모든 도시를 방문한 것은 맞지만 마지막 도시에서의 출발 도시로 다시 갈 수 있는지 확인하고 그 값을 더해줘야 한다.

if (depth == N - 1 && arr[now][start] != 0) {
    answer = Math.min(answer, cost + arr[now][start]);
    return;
}

---

🗝 풀이 코드

1차 풀이코드

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

public class Main {

    static int N, answer;
    static boolean[] isVisited;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        answer = Integer.MAX_VALUE;
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

        for (int i = 0; i < N; i++) {
            isVisited = new boolean[N];
            isVisited[i] = true;
            backtracking(i, i, 0, 0);
        }

        System.out.println(answer);
    }

    private static void backtracking(int start, int now, int depth, int cost) {
        if (depth == N - 1 && arr[now][start] != 0) {
            answer = Math.min(answer, cost + arr[now][start]);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!isVisited[i] && arr[now][i] != 0) {
                isVisited[i] = true;
                backtracking(start, i, depth + 1, cost + arr[now][i]);
                isVisited[i] = false;
            }
        }
    }
}

 

 

다른 사람의 풀이 코드를 보다 신기한 것을 발견했는데 어느 도시를 시작점으로 삼아도 최소비용은 같은 결과를 반환한다는 것이다. 이를 적용하면 굳이 for문을 돌려서 모든 도시를 출발하지 않고 1번 도시만 시작해도 같은 최소비용을 구할 수 있다.

출처 : https://lotuslee.tistory.com/92

 

2차 풀이코드

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

public class Main {

    static int N, answer;
    static boolean[] isVisited;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        answer = Integer.MAX_VALUE;
        arr = new int[N][N];

        for (int i = 0; i < N; i++) {
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }

//        for (int i = 0; i < N; i++) {
//            isVisited = new boolean[N];
//            isVisited[i] = true;
//            backtracking(i, i, 0, 0);
//        }
        
        isVisited = new boolean[N];
        isVisited[0] = true;
        backtracking(0, 0, 0, 0);

        System.out.println(answer);
    }

    private static void backtracking(int start, int now, int depth, int cost) {
        if (depth == N - 1 && arr[now][start] != 0) {
            answer = Math.min(answer, cost + arr[now][start]);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!isVisited[i] && arr[now][i] != 0) {
                isVisited[i] = true;
                backtracking(start, i, depth + 1, cost + arr[now][i]);
                isVisited[i] = false;
            }
        }
    }
}

 

확실히 시간이 거의 2배 가까이 줄어든 것을 확인할 수 있었다.