[백준] 10971.외판원 순회 2

@BackTracking / 28m (생각, 필기 20분)

알고리즘 쉰지 너무 오래돼서.. 이거 뭘로 풀어야하지 크루스칼인가.. 멍때리다가

생각하다가 떠올림

 

 

문제 링크

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

 

풀이 방법

1. 시작점으로 다시 돌아와야 한다 -> 즉, 어떤 점에서 출발하든 상관 없다 라는 의미임

예를 들면 1->2->3->4->1로 가는 경로라면, 2->3->4->1->2도 같은 경로이다.

모든 점을 다 지나야 하므로, 그냥 임의의 점에서 출발시키면 된다.

처음에는 이 생각을 못하고 모든 출발점마다 돌게 했었다..ㅎㅎㅎ

 

2. 시작점으로 다시 돌아와야 하므로

한번은 중복이 있어야 하는데, 두가지 방법이 있다.

 

1) 시작점에서는 visit 체크를 안 하고

N번 이동하고 시작점과 끝점이 같은 경우에만 최소비용을 갱신한다

-> 이렇게 하면, 불필요한 실행들이 많아진다. 시작점에서 visit체크를 안하고 시작하므로 중간에 시작점을 또 들를 수도 있다

 

2) 시작점에서 visit 체크를 하고

N-1번 이동하고, 마지막 점에서 시작점을 잇는 경로가 있는 경우에만 최소비용을 갱신한다

-> 이렇게 하면 불필요한 실행이 없어져서 시간이 반 가까이 줄어든다

단, 이렇게 하려면 반드시 시작점에서 visit 체크를 해야한다. 빼먹고 했다가 시작점을 처음, 중간, 마지막까지 방문하는 불상사가..

 

 

코드

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

public class Main {
	
	static int N, cost[][], min = Integer.MAX_VALUE;
	static boolean visit[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		visit = new boolean[N];
		cost = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				cost[i][j] = Integer.parseInt(st.nextToken());
		}
		
		visit[0] = true;				//이거 없으면 틀림. 중간에 얘 방문 할 수도 있어서..
		backTracking(0, 0, 0, 0);
		System.out.println(min);
	}

	private static void backTracking(int start, int now, int depth, int sum) {
		if (depth == N - 1) {
			if (cost[now][start] != 0)	//시작점으로 돌아가는 경로가 존재한다면 
				min = Math.min(min, sum + cost[now][start]);
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (visit[i] || cost[now][i] == 0) continue;
			
			if (sum > min) return;
			
			visit[i] = true;
			backTracking(start, i, depth + 1, sum + cost[now][i]);
			visit[i] = false;
		}
	}
}

많이 빨라졌네..ㅎㅎ

끗!