[백준 / Java] 10971번: 외판원 순회2 (실버2)

문제 풀이 날짜: 2023.05.11
포스트 작성일: 2023.05.25

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 10971번: 외판원 순회2 (실버2) (문제 링크)

 

키워드

DFS, 백트랙킹

 

풀이 접근법

• 실버2의 외판원 순회는 입력이 2 ≤ N ≤ 10 이기 때문에 백트랙킹으로 풀이 가능하다.
  • 골드1 등급에도 외판원 순회1이 있는데, 해당 문제는 입력이 2 ≤ N ≤ 16이므로 백트랙킹이 아닌 다른 방식으로 풀이해야 한다.
• 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로 ⇒ DFS로 모든 도시를 방문하며 비용을 누적시키고, 마지막 도시로부터 출발지로 돌아가는 비용까지 누적시킨다. 
  • 경로는 각 마을을 출발지로 삼아서 한 번씩 계산한다.
  • DFS에서 탐색할 후보는 '현재 위치 u에서 갈 수 있는 모든 v들'이다.
• 또, 마지막 마을에서 첫 번째 마을로 곧바로 올 수 있는 경로는 최소 한 가지 이상 존재하도록 케이스가 구성되어 있다.
  • 그러나 (DFS의 깊이 == N)에 도달했을 때 반드시 첫 번째 마을로 돌아오는 경로가 있다는 것을 보장할 수 없다. 따라서 해당 마을에서 첫 번째 마을로 돌아오는 경로가 있는지를 반드시 체크하고 비용을 더해주어야 한다.
  • 각 마을마다로 시작점을 달리해서 출발해야 하는데, 출발하는 마을의 visited를 true로 바꾸고 DFS를 시작해야 한다는 점도 주의하자. 

 

코드

import java.util.*;
import java.io.*;

public class Q10971 {

	private static boolean[] visited;
	private static int[][] weight;
	private static int answer = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		visited = new boolean[N];
		weight = new int[N][N];

		StringTokenizer st;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				weight[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0; i < N; i++) {
			visited[i] = true; //여기서 시작하기 때문에 depth = 1로 초기화 
			
			DFS(i, i, N, 1, 0);

			visited = new boolean[N];
		}
		
		System.out.print(answer);
	}
	
	public static void DFS(int start, int curr, int N, int depth, int length) {
		
		if(N == depth) {
			if(weight[curr][start] != 0) {
				answer = Math.min(length + weight[curr][start], answer);
			}
			return;
		}
		
		for(int i = 0; i < N; i++) {
			if(!visited[i] && weight[curr][i] != 0) {
				visited[i] = true;
				
				DFS(start, i, N, depth + 1, length + weight[curr][i]);
				
				visited[i] = false;
			}
		}
		
		return;
	}

}

---

백트랙킹 문제의 응용판 중 하나로, 시작점을 바꿔가며 각 마을마다 DFS를 해야한다는 점을 기억하고 전체 비용을 계산할 때 첫 번째 마을로 되돌아가야 한다는 조건만 빠트리지 않으면 어렵지 않게 풀 수 있다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day6/Q10971.java