문제

외판원 순회 2

풀이

외판원 순회 문제는 처음이다. 이 문제는 최대 도시가 10개 이기 때문에 모두 방문해서 가장 작은 값을 갱신해주면 된다.

1. 처음에 방문 할 곳을 정한다

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

2. 전체 경로를 전부 방문해서 가장 작은 비용을 갱신한다

private static void dfs(int start, int current, int cost) {
	// 현재 모두 방문 된 비용인지 확인
    if (isValid()) {
    	// 순환이 가능한 방문지인지 확인하기
        if (arr[start][current] != 0) {
        	// 현재 금액(current에서 0번째 인덱스까지 연결된 금액)
            // 이 현재 비용보다 작으면 갱신한다
        	answer = Math.min(answer, cost + arr[current][0]);
        }
    }
    
    for (int i = 1; i < n; i++) {
    	// 이미 순회가 된 것인지 확인하고 연결되어 있는지까지 확인해야 함
        if (!visited[i] && arr[current][i] != 0) {
        	visited[i] = false;
            dfs(start, i, cost + arr[current][i]);
            visted[i] = true;
        }
    }
}

// 전체 구역을 전부 방문 한 내용인지 확인
private static boolean isValid() {
	for (int i = 0; i < n; i++) {
    	if (!visited[i]) {
        	return false;
        }
    }
    return true;
}

전체 코드

전체 코드