SW Expert Academy [S/W 문제해결 기본] 3일차 - 최적 경로 [C++]

 

#문제 간단 정리

dfs 를 이용한 완전탐색

#문제 해결 방법

 우선 거리를 측정하는 방법을 알려 준 것이 힌트라고 생각한다.

처음에는 순간 map 을 이용하는 방법이 떠올랏지만

거리를 단순히 두 좌표의 차이를 더해서 구해주기 때문에

두 거리의 좌표 차들만 순회해서 (완전탐색) 으로

조회해서 최대 거리만 구해주면 답을 구할 수 있다 (10!)

 

#전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <iomanip>
#include <tuple>
#include <sstream>
#include <map>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;

bool visited[10];
int result;
vector<pair<int, int>> clients;
pair<int, int> company;
pair<int, int> house;

void dfs(int idx, int dist , pair<int,int> now ) {
    if (idx == clients.size()) {
        dist += abs(now.first - house.first) + abs(now.second - house.second);
        if (dist < result) {
            result = dist;
        }
    }


    for (int i = 0; i < clients.size(); i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(idx +1, dist + (abs(now.first - clients[i].first) + abs(now.second - clients[i].second)), clients[i]);
            visited[i] = false;
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int tc;
    cin >> tc;

    for (int i = 0; i < tc; i++) {
        int n;
        cin >> n;

        cin >> company.first >> company.second;
        cin >> house.first >> house.second;

        clients.resize(n);
        for (int j = 0; j < n; j++) {
            cin >> clients[j].first >> clients[j].second;
        }

        memset(visited, false, sizeof(visited));
        result = INT_MAX;
        dfs(0, 0, company);

        cout << '#' << i+1 << ' ' << result << '\n';
        
    }
        
    return 0;
}