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

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

문제

---

풀이

한 도시에서 시작하여 모든 도시 경로를 탐색하는 완전 탐색을 활용한다

1. 한 도시를 출발점으로 정하여 재귀를 시작한다

2. 현재 도시에서 방문하지 않은 도시로 이동한다

3. 모든 도시를 방문했다면 마지막 도시에서 출발점으로 돌아오는 비용을 더한다

4. 최솟값을 갱신한다

 

자세한 것은 코드를 보자

코드

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


public class Main {

	static int N;
	static boolean[] visited; // 방문 배열
	static int[][] arr; // 뽑아낸 수

	static int minCost = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		N = Integer.parseInt(br.readLine());
		// 초기화
		visited = new boolean[N];
		arr = new int[N][N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 0; i < N; i++) {
			visited[i] = true; // 시작 지점 방문 처리
			recur(i, i, 0, 0); // 0번 도시부터 재귀 호출
			visited = new boolean[N]; // 방문 배열 초기화
		}

		System.out.println(minCost);

		br.close();
	}

	static void recur(int start, int cur, int depth, int cost) {
		// 현재 비용이 최소 비용을 넘었다면 return
		if (cost >= minCost) {
			return;
		}

		// N개의 도시를 모두 방문했을 경우
		if (depth == N - 1) {
			// 마지막 도시에서 출발 도시로 돌아올 수 있는지 확인
			if (arr[cur][start] != 0) {
				// 최솟값 갱신
				minCost = Math.min(minCost, cost + arr[cur][start]);
			}
			return;
		}

		for (int i = 0; i < N; i++) {
			// 방문했거나 갈 수 없는 경우면 continue
			if(visited[i] || arr[cur][i] == 0) continue;
			visited[i] = true; // 방문 처리
			recur(start, i, depth + 1, cost + arr[cur][i]); // 비용을 더해줌
			visited[i] = false; // 다음을 위해 false 처리
		}
	}

}

결과