백준 10971. 외판원 순회 2

🅰 백준 10971. 외판원 순회 2

10971번: 외판원 순회 2

✏️ 문제 풀이

• 순열을 이용하여 모든 출발점에서 돌 수 있는 경우의 수를 뽑아낸 다음 비용을 계산해주었다.
• 순열이 완성되면 비용행렬을 탐색하면서 가는 길이 없으면 비용들을 다 더했더라도 boolean변수를 이용하여 최소값으로 비교하지 못하게 하였다.

✏️ 소스코드

package bruteforce;

import java.util.*;
import java.io.*;
/*
 * 외판원 순회2 문제
 * 모든 노드들에 대해 순열을 하여 경우의 수를 파악한 후
 * 그 경우에 수에 따라 map에서 데이터를 더해준다.
 * 만약 연결되지 않은 노드 즉, map[x][y] == 0이라면 길이 없는 경우기 때문에 종료한다.*/
public class Main_실버2_10971_손은성 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int input[] = new int[N];
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			input[i] = i;
		}
		int map[][] = new int[N][N];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		do {
			int sum = 0;
			boolean find = false;
			for (int i = 0; i < N-1; i++) {
				if(map[input[i]][input[i + 1]] == 0) find = true;   // break 해버리면 for문을 나가고, 밑에 N-1->0으로 가는 길이 있다면 답을 출력해버리는 문제가 있음 
																	// 그래서 boolean을 이용하여 if문안에서 0이면 수행을 못하게 함.
				sum += map[input[i]][input[i + 1]];
			}
			if(find||map[input[N-1]][input[0]] == 0)
				continue;
			sum+=map[input[N-1]][input[0]];
			min = Math.min(min, sum);
		} while (np(input));
		System.out.println(min);
	}

	//nextpermutation
	static boolean np(int input[]) {
		int N = input.length - 1;

		int i = N;
		while (i > 0 && input[i - 1] >= input[i])
			--i;
		if (i == 0)
			return false;

		int j = N;
		while (input[i - 1] >= input[j])
			--j;
		swap(input, i - 1, j);

		int k = N;
		while (i < k)
			swap(input, i++, k--);

		return true;
	}

	static void swap(int input[], int i, int j) {
		int temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}
}

 

✅ 후기

• 다시 돌아보니 백트래킹으로 풀 수 있을 것 같은데 모든 경우의 수를 생각해서 풀었던 것 같다. 백트래킹으로 다시한번 풀어봐야겠다.