https://www.acmicpc.net/problem/10971

 

10971번: 외판원 순회 2

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

흠 실버 치고 조금 난이도가 있네요  

비용이 싼순서로 바로 탐색하는게 아니라  모든 경로를 탐색해서 그합이 가장 낮은걸 찾는게 key point네요 

#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
#include<cmath>
using namespace std;

void Prints(vector<vector<char>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j]<< ",";
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j]<< ",";
		}
		cout << endl;
	}
	cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cout << maps[i][j]<<",";
		}
		cout << endl;
	}
	cout << endl;
}
struct Point {
	int s;
	int e;
	int cnt;
};
struct Data {
	int index;
	vector<bool> bVisitied;
	int cnt=0;
	int gc = 1;

};

int main() {
	int n;
	vector<vector<int>>maps;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		vector<int>tmpMaps;
		for (int j = 0; j < n; j++) {
			int tmp;
			cin >> tmp;
			tmpMaps.push_back(tmp);

		}
		maps.push_back(tmpMaps);
	}
	//Prints(maps, n, n);
	//0 1 2 3 
	vector<bool>bVisitied(n, false);
	vector<int>vGsum;
	int gsum = 0;
	for (int z = 0; z < n; z++) {
		int gStart = 0;
		int gEnd = 0;
		int count = 0;
	
		queue<Data>q;
		Data p;
		p.index = z;
		p.bVisitied = bVisitied;
		gStart = z;
		q.push(p);
		
		int sum = 0;
		
		while (!q.empty()) {
			
			Data start=q.front();
			
			q.pop();
			count++;
			int max = 1e9;
			int arrvie = start.index;
			for (int j = 0; j < n; j++) {
				if (start.index != j) {
					if (start.bVisitied[j]==false&&maps[start.index][j]!=0&&j!=gStart) {
						max=maps[start.index][j];
						arrvie = j;
						
						sum += max;
						bVisitied[j] = true;
						Data tmpD;
						tmpD.index = arrvie;
						tmpD.cnt = start.cnt + maps[start.index][j];
						tmpD.gc = start.gc + 1;
						start.bVisitied[j] = true;
						tmpD.bVisitied = start.bVisitied;
						start.bVisitied[j] = false;
						gEnd = arrvie;
						q.push(tmpD);
						
						
					}
					else if (start.gc==n&&j==gStart&& maps[start.index][j] != 0&& start.bVisitied[j] == false) {
						max = maps[start.index][j];
						arrvie = j;
						if (gsum == 0) {
							gsum = start.cnt + maps[start.index][j];
							
						}
						else {
							if (gsum > start.cnt + maps[start.index][j]) {
								gsum = start.cnt + maps[start.index][j];
								
							}
						}
						sum += max;
						bVisitied[j] = true;
						Data tmpD;
						tmpD.index = arrvie;
						tmpD.cnt = start.cnt + maps[start.index][j];
						tmpD.gc = start.gc + 1;
						start.bVisitied[j] = true;
						tmpD.bVisitied = start.bVisitied;
						start.bVisitied[j] = false;
						gEnd = arrvie;
						q.push(tmpD);
						
					}
					
				}
			}
		}
	}
	cout << gsum;


	return 0;
}

'알고리즘 공부' 카테고리의 다른 글

백준 영역 구하기  (0) 2023.07.15
백준 바이러스  (0) 2023.07.15
백준 반복수열  (0) 2023.07.13
백준 순열 사이클  (0) 2023.07.13
백준 촌수계산  (0) 2023.07.13

+ Recent posts