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문제임.

좋은 웹페이지 즐겨찾기