[백준 Silver 2] 10971 외판원 순회2 - Java

문제링크 : https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

접근 과정 : 

• 한 도시에서 출발하여 모든 도시를 방문한 뒤, 출발 도시로 돌아왔을 때의 비용이 가장 적은 것을 출력하는 문제.
• 방문체크를 하면서 완전탐색을 하는 방법을 생각
• 도시의 수가 최대 10개이기에, 비용을 저장한 배열을 그냥 탐색하면서 다음 경로를 추적.
• 방문체크는 비트를 이용하여 판단
• 비용을 누적해가면서 경로를 추적하다가, 만약 이미 갱신된 최저비용보다 현재 비용이 더 많다면 그 경로는 중단 

 

소스 코드 및 결과 :

package BOJ;

/* 
    외판원 순회 2
*/

import java.io.*;
import java.util.*;

public class BOJ10971 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        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());
            }
        }

        minCost = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            travel(i, i, 0, 0);
        }

        System.out.println(minCost);

    }

    static int N;
    static int[][] map;
    static int minCost;

    static void travel(int start, int now, int visit, int cost) {

        if(cost > minCost){
            return;
        }

        if (visit == (1 << N)-1 && start == now) {
            minCost = Math.min(minCost, cost);
            return;
        }

        for (int i = 0; i < N; i++) {
            if (map[now][i] == 0 || (visit | (1 << i)) == visit) {
                continue;
            }

            travel(start, i, visit | (1 << i), cost + map[now][i]);
        }

        return;
    }
}

 

P.S 

조건이 도시에 한번만 방문해야한다는 것 뿐이었고, 도시의 개수가 크지 않아서 크게 어려운 문제는 아니었다.

TSP로 불리는 중요한 유형이라는데... 비슷한 다른 문제도 풀어봐야겠다.

+ (최저 비용 > 현재 비용) 부분 체크안하니까, 많은 시간이 소모되더라.