#106. [백준_C언어] 10971 : 외판원 순회 2 \ 백트래킹

 

입력 코드

#include <stdio.h>

int p[10][10], N, min = 10000000;
char vt[10];

void tsp(char k, char d, int v) {
	char i;
	if (vt[k] || v >= min) return;
	if (d == N - 1) {
		if (p[k][0] && v + p[k][0] < min) min = v + p[k][0];
		return;
	}
	vt[k] = 1;
	for (i = 1 ; i < N ; i++)
		if (p[k][i]) tsp(i, d + 1, v + p[k][i]); 
	vt[k] = 0;
}

int main() {
	int i, j;
	scanf("%d", &N);
	for(i = 0 ; i < N ; i++)
		for (j = 0 ; j < N ; j++)
			scanf("%d", &p[i][j]);
	tsp(0, 0, 0);
	printf("%d\n", min);
}

출처 www.acmicpc.net/source/4405809

 

 

코드 설명

#백트래킹 #외판원 순회 문제

 

 

문제 출처

www.acmicpc.net/problem/10971

10971번: 외판원 순회 2