[백준 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) 방문하도록 했다.

 

소스코드 :