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

문제

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

풀이1

 재귀함수를 생각했다. 만약 방문한 도시의 수가 N개이면 최솟값을 구한다. 방문한 도시의 수가 N개가 아니면 다음 방문할 도시를 찾는다. 

이때 다음 방문할 도시는 이전에 방문한적이 없는 도시이면서, 현재방문한 도시와 연결되어 있어야 한다. 

 

public static int getMinCost(int currentNode, int visitCount){
	if(visitCount>=N){
    	//	최솟값 구하기
     }
     else{
     //현재노드(currentNode)를 visitCount번째에 방문했을 때 최솟값
     int min = Integer.MAX_VALUE; 
     	
        //다음 방문노드 구하기
     	for(int node = 0; node<N; node++){
        	if(!visited[node] && prices[currentNode][node]){
            	visited[node] =true;
                cities[visitCount] = node;
                int result = getMinCount(node, visitCount+1);
                
                min = Integer.min(min,result);
                visited[node] =false;
            }
        }
      }
 }
                

 

위의 함수는 currentNode를 visitCount번째에 방문했을 때의 최솟값을 return한다. 

 

그럼 이제 visitCount >=N일 때 최솟값을 구해야한다. 순회한다는 조건에서 주의해야할 점은 cities의 맨마지막 요소는 cities의 맨 첫번째요소와 연결되어 있어야 한다는 것이다. 따라서 만약 맨 마지막 요소와 맨 첫번째 요소가 연결되어 있지 않으면 Integer.MAX_VALUE를 반환한다.

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] prices;
    static int[] cities;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        prices = new int[N][N];
        cities = new int[N];
        visited = new boolean[N];

        for(int r=0;r<N; r++){
            st = new StringTokenizer(br.readLine()," ");
            for(int c=0; c<N; c++){
                prices[r][c] = Integer.parseInt(st.nextToken());
            }
        }

        int min = Integer.MAX_VALUE;
        for(int start = 0; start<N; start++){
            cities[0] = start;
            visited[start] = true;
            int result = getMinCost(start,1);

            visited[start] = false;
            min = Math.min(min,result);
        }

        bw.write(String.valueOf(min));
        bw.flush();

    }
    public static int getMinCost(int currentNode, int visitCount){
        if(visitCount>=N){
            if(prices[cities[N-1]][cities[0]]!=0){
                int result = 0;
                for(int i=0; i<cities.length;i++){
                    if(i==cities.length-1){
                        result += prices[cities[i]][cities[0]];
                    }
                    else{
                        result +=prices[cities[i]][cities[i+1]];
                    }
                }
                return result;
            }
            return Integer.MAX_VALUE;
        }
        else{
            int min = Integer.MAX_VALUE;
            for(int node = 0; node<N; node++){
                if(prices[currentNode][node]!=0 && !visited[node]){
                    visited[node] = true;
                    cities[visitCount] = node;
                    int result = getMinCost(node, visitCount+1);

                    visited[node] =false;
                    min = Integer.min(result, min);
                }
            }
            return min;
        }
    }
}