[백준] 10971 : 외판원 순회 2 (JAVA)

문제

BOJ 10971 : 외판원 순회 2 - https://www.acmicpc.net/problem/10971

풀이

Traveling Salesman problem(TSP), 외판원 순회의 기본적인 문제이다.

DFS로 풀이하면 되는 문제! 모든 지점을 방문하는 최소 비용을 구한다. 방문 여부를 체크해서 한번 방문했던 도시는 다시 방문할 수 없다 라는 조건을 만족시켜야 한다.

도시 간의 비용이 0일 경우 갈 수 있는 루트가 없는 것이기 때문에 dfs의 조건을 A 도시를 방문하지 않았으며 A 도시로 가는 루트가 존재할 경우 - if (!visited[i] && map[now][i] != 0)으로 정의했다.

모든 도시를 방문했고, 마지막 도시에서 처음 도시로 가는 루트가 존재하면 cost를 비교하여 최솟값을 알아낸다.

출발 지점을 문제에서 지정해주지 않았기 때문에 모든 도시를 출발지로 한번씩 dfs()를 호출한다.

코드

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

public class Main {
    static int n;
    static boolean[] visited;
    static int[][] map;
    static long result_min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++) {
            visited = new boolean[n];
            visited[i] = true;
            dfs(i, i, 0);
        }
        System.out.println(result_min);
    }

    public static void dfs(int start, int now, long cost){
        if (allVisited()) {
            if(map[now][start]!=0){
                result_min = Math.min(result_min, cost+map[now][0]);
            }
            return;
        }

        for(int i=1; i<n; i++){
            if (!visited[i] && map[now][i] != 0) {
                visited[i] = true;
                dfs(start, i, cost + map[now][i]);
                visited[i] = false;
            }
        }
    }

    public static boolean allVisited() {
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

}

정리

✔ 알고리즘 분류 - 브루트포스 알고리즘, 백트래킹, 외판원 순회 문제
✔ 난이도 - ⚪ Silver 2

🤦‍♀️ 오늘의 메모

• 전형적인 DFS 문제라 크게 어렵지는 않았던 문제. 다만 처음에 문제 조건을 제대로 안보고 첫번째 도시만 출발지가 되는 줄 알고 풀었는데, 지금 정리하다보니 모든 도시가 출발지가 된다는 걸 알았다. (근데 전자로 풀었을때도 맞았습니다가 떠서 몰랐다.. 문제 테스트 케이스가 세세하지 않은듯)
  
  아래는 첫번째 도시(index는 0)만 출발지가 되는 경우로 풀이한 코드.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        visited = new boolean[n];
        visited[0] = true;
        dfs(0, 0); // dfs 한번만
        System.out.println(result_min);
    }

    public static void dfs(int now, long cost){
        if (allVisited()) {
            if(map[now][0]!=0){ // 첫번째 도시로 가는 길이 있을 경우
                result_min = Math.min(result_min, cost+map[now][0]);
            }
            return;
        }

        for(int i=1; i<n; i++){
            if (!visited[i] && map[now][i] != 0) {
                visited[i] = true;
                dfs(i, cost + map[now][i]);
                visited[i] = false;
            }
        }
    }

• (추가) 스터디를 진행하며 개념을 정리하다보니 추가적으로 알게된 내용. 다음과 같이 어느 정점에서 출발하던 최소비용은 모두 같다!! 그래서 하나의 정점에서 출발하는 것으로 코드를 짜도 정답이 나왔나보다. 신기해라
  [출처] https://lotuslee.tistory.com/m/92?category=848933
  
  

참고 사이트

딱히 없음