백준 10971번: 외판원 순회 2

문제 설명

• https://www.acmicpc.net/problem/10971
• 외판원 문제입니다. 시작점 -> 모든 노드 -> 다시 시작점으로 돌아오는 비용을 구하는 문제입니다.

접근법

• N가지 경로를 백트래킹으로 만든 뒤 마지막 위치에서 시작점까지 돌아오는 거리비용을 더해주는 방식으로 풀었습니다.
  • 다시 고민해보니 이 방식이 더 좋아보입니다.
    • 정답배열을 N+1만큼 만든 다음 처음 BackT함수에 넘겨줄때 마지막 값을 채워서 넘겨줍니다.
    • 예시 {B,0,0,0,B}

정답

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

public class Main {
	static int minVal = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		int[][] board = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i = 0; i < N; i++) {
			int[] answer = new int[N];
			answer[0] = i;
			
			boolean[] v = new boolean[N];
			v[i] = true;
			BackT(i,i, N, 0, v, answer, 0, board);
		}
		System.out.println(minVal);
	}

	public static void BackT(int start,int now, int N, int depth, boolean[] v, int[] answer, int Score, int[][] board) {
		
		if (N == depth+1) {
			if(board[now][start] == 0) return; // 돌아갈 수 없는 경우
			minVal = Math.min(minVal, Score+board[now][start]);
			return;
		}

		for (int i = 0; i < N; i++) {
			if (v[i]) continue; // 이미 방문한 위치
			if(board[now][i] == 0) continue; // 길이 없는 경우
			v[i] = true;
			answer[depth+1] = i;
			BackT(start,i, N, depth + 1, v, answer, Score + board[now][i], board);
			v[i] = false;
		}
	}
}