[백준 10971번] 외판원 순회 2 (java)

10971번: 외판원 순회 2

 

어느 한 도시에서 출발하여 모든 도시를 거친 후, 처음으로 돌아오는 문제이다.

여기서 알아야 할 사실은 어느 도시에서 출발하든 가장 적게 드는 비용은 동일하다는 것이다.

 

 

 

따라서 아무나 한 곳을 시작도시로 정해서 dfs를 사용하여 시작한 곳으로 돌아오면 된다.

모든 도시를 한 번씩만 방문해야하므로 visited 배열을 이용하여 방문 여부를 표시한다.

 

그런데 문제를 풀면서 한가지 헷갈렸던 점이 있다.

처음 시작한 도시는 이미 처음에 방문처리가 될 것이다. 각 도시마다 방문 여부를 확인한 뒤 방문하지 않은 도시만 방문하는데, 마지막에 다시 처음 도시로 돌아올 때는 해당 도시가 이미 방문처리 되어있기 때문에 이에 대한 처리를 별도로 해줘야 한다.

 

그래서 시작도시를 갈 수 있는 방법은 방문 여부와 관계없이 방문한 도시 개수를 카운트하여, 모든 도시를 다 방문했을 때만 시작도시를 다시 갈 수 있도록 했다.

if (n == start && cnt == N) { // 인접한 도시가 시작도시이고, 모든 도시를 다 방문한 상태인 경우
	cost += w[now][n];
	dfs(start, n, cnt + 1, cost);
}

 

시작도시가 아닌 나머지 도시는 아직 방문하지 않았을 때만(visited[n] = false) 방문하도록 했다.

 

소스코드 : 

	import java.io.*;
	public class n10971 {
	static int N;
	static int[][] w;
	static boolean[] visited;
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	N = Integer.parseInt(br.readLine());
	w = new int[N + 1][N + 1];
	visited = new boolean[N + 1];
	for (int i = 1; i <= N; i++) {
	String[] sarr = br.readLine().split(" ");
	for (int j = 1; j <= N; j++) {
	w[i][j] = Integer.parseInt(sarr[j - 1]);
	}
	}
	visited[1] = true;
	dfs(1, 1, 1, 0);
	bw.write(min + "\n");
	bw.flush();
	}
	public static void dfs(int start, int now, int cnt, int cost) {
	if (now == start && cost > 0) {
	min = Math.min(min, cost);
	return;
	}
	for (int n = 1; n <= N; n++) {
	if (w[now][n] > 0) {
	if (n == start && cnt == N) {
	cost += w[now][n];
	dfs(start, n, cnt + 1, cost);
	}
	else if (!visited[n]) {
	visited[n] = true;
	cost += w[now][n];
	dfs(start, n, cnt + 1, cost);
	cost -= w[now][n];
	visited[n] = false;
	}
	}
	}
	}
	}

view raw 10971.java hosted with ❤ by GitHub