[알고리즘] 백준 10971 외판원 순회 2 -백트래킹- 자바

 

 

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

 

 

백준 백트래킹 유형에서 외판원 순회2 라는 문제를 풀어봤습니다. ㅎㅎ 

 

N개의 도시를 특정 시작 도시에서 출발하여 다시 첫 도시로 순회하는 최단 경로를 구하는 문제입니다. 방문한 도시는 다시 못가고요.

 

백트래킹을 사용하면 되고 매개변수로 깊이, 시작도시, 이전방문도시, 총 경로비용, 방문 여부를 사용해주면 됩니다.

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {
    private static int N; // 도시의 수
    private static int[][] map; // 경로
    private static boolean[] isVisited; // 도시 방문 여부
    private static int answer = Integer.MAX_VALUE;


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];
        isVisited = new boolean[N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < N; i++) {
            isVisited[i] = true;
            dfs(0, i, i, 0, isVisited);
        }
        System.out.println(answer);
    }

    private static void dfs(int depth, int start, int prev, int cost, boolean[] isVisited) { // 깊이, 첫시작도시, 이전탐색도시, 총비용, 도시 방문여부
        if (depth == N - 1) {
            if (map[prev][start] != 0) {
                answer = Math.min(answer, cost + map[prev][start]); // 다시 시작점으로 돌아오는 경우 플러스
            }
            return;
        }
        for (int i = 0; i < N; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                if (map[prev][i] != 0) {
                    dfs(depth + 1, start, i, cost + map[prev][i], isVisited);
                }
                isVisited[i] = false;
            }
        }
    }
}

github.com/mtjin/algorithm_practice/tree/master/%EB%B0%B1%EC%A4%80%2010971%20%EC%99%B8%ED%8C%90%EC%9B%90%20%EC%88%9C%ED%9A%8C%202%20-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-

mtjin/algorithm_practice

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!