SWEA1247. 최적경로
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD
#include <iostream>
#include <vector>
using namespace std;
pair<int, int> home;
pair<int, int> company;
vector <pair<int, int>> customers;
bool check_visit[10];
int Min;
bool chk[10] = { false };
int sumf(int x1, int y1, int x2, int y2)
{
return abs(x1 - x2) + abs(y1 - y2);
}
void dfs(int sum, int startx, int starty, int cnt)
{
if (cnt == customers.size())
{
int iTemp = sum + sumf(startx, starty, home.first, home.second);
if (iTemp < Min) Min = iTemp;
}
for (int i = 0; i < customers.size(); i++)
{
if (chk[i] == false)
{
int newx = customers[i].first;
int newy = customers[i].second;
chk[i] = true;
dfs(sum + sumf(startx, starty, newx, newy), newx, newy, cnt + 1);
chk[i] = false;
}
}
}
int main() {
int T;
cin >> T;
for (int i = 1; i <= T; i++) {
int N;
Min = 987654321;
cin >> N;
customers.resize(N);
for (int n = 0 ; n < 10; n++)
{
chk[n] = false;
}
cin >> company.first >> company.second >> home.first >> home.second;
for (int j = 0; j < N; j++)
cin >> customers[j].first >> customers[j].second;
dfs(0, company.first, company.second, 0);
cout << "#" << i << " " << Min << "\n";
}
return 0;
}
전형적인 DFS문제임.
Author And Source
이 문제에 관하여(SWEA1247. 최적경로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@imalive77/SWEA1247.-최적경로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)