[백준 10971] 외판원 순회 2
문제 설명
N개의 도시를 모두 순회할 때 필요한 경비의 최소값을 구하는 문제이다.
- 마지막 도착지에서 끝나는 것이 아니고, 마지막 여행지 -> 처음 출발지로 돌아와야 한다.
각 도시간 이동하는데 드는 비용이 0이라면, 도시간 이동이 불가능함을 나타낸다.
- 즉, 이 경우에는 모든 도시를 순회할 수 없다.
생각 정리
// 함수실행 (파라미터 : 현재 방문하는 도시의 순서, 즉 ?번째인지)
// N == 현재 방문한 도시의 개수 (N개의 도시를 방문하는 순서가 정해진 상태)
//경로배열의 마지막에 출발지 추가
//해당 순서로 이동할 때의 비용 계산
//이 때, 0이 나오면 이동이 불가 ==>
//모든 도시를 거칠 수 없음 ==>
//그냥 리턴하자
//최소비용을 업데이트한다
//리턴
// N개의 도시를 순회하면서 (N개의 도시를 순회하는 순서를 찾아내기 위함)
//방문을 하지 않았다면
//방문하고
//해당 도시를 배열에 추가(=함수의 파라미터로 전달받은 ?번째 여행지에 추가)
//다음 방문순서를 파라미터로 함수 호출
//방문해제
완성
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ10971 {
static int N, answer = 0;
static int[][] W;
static boolean[] visited;
static int[] path;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = new int[N+1][N+1];
visited = new boolean[N+1];
path = new int[N+1];
for(int i=1; i<=N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<=N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
tsp(0);
System.out.println(answer);
}
static void tsp(int curr) {
if(curr == N) {
int cost = 0;
path[N] = path[0]; //출발지로 다시 돌아와야하기 때문에 맨 마지막에 출발지를 넣음
for(int i=0; i<N; i++) {
if(W[path[i]][path[i+1]] == 0){
return ;
}
cost += W[path[i]][path[i+1]];
}
if(answer == 0)
answer = cost;
else
answer = Math.min(answer, cost);
return ;
}
for(int i=1; i<=N; i++) {
if(!visited[i]) {
visited[i] = true;
path[curr] = i;
tsp(curr+1);
visited[i] = false;
}
}
}
}
Author And Source
이 문제에 관하여([백준 10971] 외판원 순회 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@like02_like0/백준-10971-외판원-순회-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)