728x90
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
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
void SearchCity(int startCity, int currentCity, int costSum, int count, vector<vector<int>> visitedCityArr, vector<bool> visitedCityVector);
int leastCost = INT_MAX;
int main() {
int cityNum, input;
cin >> cityNum;
vector<vector<int>> cityVector(cityNum, vector<int>(cityNum, 0));
vector<bool> visitedCityArr(cityNum, false);
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
cin >> cityVector[i][j];
}
}
//ํ์ gogo
for (int city = 0; city < cityNum; city++) {
SearchCity(city, city, 0, 0, cityVector, visitedCityArr);
}
cout << leastCost;
//๋์ ํ ๋น ํด์
for (int i = 0; i < cityNum; i++) {
cityVector[i].clear();
} cityVector.clear();
visitedCityArr.clear();
return 0;
}
void SearchCity(int startCity, int currentCity, int costSum, int count, vector<vector<int>> cityVector, vector<bool> visitedCityVector) {
if (currentCity == startCity && count == cityVector.size()) {
if (leastCost > costSum) leastCost = costSum;
return;
}
for (int nextCity = 0; nextCity < cityVector.size(); nextCity++) {
if (cityVector[currentCity][nextCity] != 0 && !visitedCityVector[currentCity]) {
visitedCityVector[currentCity] = true;
costSum += cityVector[currentCity][nextCity];
if (leastCost >= costSum) SearchCity(startCity, nextCity, costSum, count + 1, cityVector, visitedCityVector);
visitedCityVector[currentCity] = false;
costSum -= cityVector[currentCity][nextCity];
}
}
}
728x90
'๐ Coding Test Study > Algorithm Problem' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++][Beakjoon] 11724๋ฒ ์ฐ๊ฒฐ์์ (0) | 2022.05.10 |
---|---|
[C++][Baekjoon][๋นํธ๋ง์คํฌ] 11723๋ฒ ์งํฉ (0) | 2022.05.08 |
[C++][Baekjoon][Math] 6588๋ฒ ๊ณจ๋๋ฐํ์ ์ถ์ธก(feat. C++ ์ ์ถ๋ ฅ ์๊ฐ ๋จ์ถ) (0) | 2022.04.03 |
[C++][Baekjoon][Math] 1978๋ฒ ์์์ฐพ๊ธฐ (0) | 2022.04.03 |
[C++][BAEKJOON] 9613๋ฒ GCDํฉ (0) | 2022.04.02 |