[SWEA 1247] 최적 경로

문제 링크

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD

SW Expert Academy

---

C++ 풀이

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

pair<int, int> home;
pair<int, int> company;
vector <pair<int, int>> customers;
bool check_visit[10];
int minD;

int cal_dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

void dfs(int sumD, int x1, int y1, int visitNum, bool check_visit[]) {
    if (sumD > minD)
        return;
    if (visitNum == customers.size()) {
        int d = cal_dist(x1, y1, home.first, home.second);
        if (sumD + d < minD)
            minD = sumD + d;
        return;
    }
    for (int i = 0; i < customers.size(); i++) {
        if (check_visit[i] == false) {
            int x2 = customers[i].first; int y2 = customers[i].second;
            check_visit[i] = true;
            dfs(sumD + cal_dist(x1, y1, x2, y2), x2, y2, visitNum + 1, check_visit);
            check_visit[i] = false;
        }
    }
    return;
}

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

    int T;

    cin >> T;
    for (int i = 1; i <= T; i++) {
        int N;
        minD = 987654321;
        cin >> N;

        customers.resize(N);
        memset(check_visit, false, sizeof(check_visit)); //visit 테이블 초기화

        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, check_visit);

        cout << "#" << i << " " << minD << "\n";
    }
    return 0;
}

 

위의 코드는 dfs로 구현한 코드이다.

 

dfs 탐색 종료 조건은 아래와 같이 두었다.

• 전체 고객 집들을 다 방문하지 않았더라도 누적된 거리가 이미 기록된 최소 거리보다 클 경우
• 전체 고객 집들을 다 방문한 경우

방문한 집들을 bool 타입의 배열(check_visit)을 사용하여 기록하였다.

 

추가적으로 배운 것은, 배열을 초기화 할 때, for 문을 통한 초기화가 아닌 memset 함수를 쓰면 더 빠르다는 것이다.

 

 

 

처음에는 아래 코드와 같이 next_permutation 함수를 사용하여 순열을 구해 문제를 풀었었다.

통과는 하였지만, 생각보다 실행시간이 길게 나와 dfs로 다시 구현하였고 실행 시간을 줄일 수 있었다.

 

 

순열로 구현한 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

pair<int, int> company;
pair<int, int> home;
int minD;

int cal_dist(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

int cal_whole_distance(vector <pair<int, int>>& customers) {
    int sum = 0;
    sum += cal_dist(company.first, company.second, customers[0].first, customers[0].second);
    for (int i = 0; i < customers.size() - 1; i++)
        sum += cal_dist(customers[i].first, customers[i].second, customers[i + 1].first, customers[i + 1].second);
    sum += cal_dist(customers.back().first, customers.back().second, home.first, home.second);
    return sum;
}

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

    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        int N;
        minD = 987654321;
        cin >> N;

        vector <pair<int, int>> customers;
        customers.resize(N);

        cin >> company.first >> company.second >> home.first >> home.second;

        for (int j = 0; j < N; j++)
            cin >> customers[j].first >> customers[j].second;

        sort(customers.begin(), customers.end());

        do {
            int distance = cal_whole_distance(customers);
            if (distance < minD)
                minD = distance;
        } while (next_permutation(customers.begin(), customers.end()));

        cout << "#" << i << " " << minD << "\n";
    }
    return 0;
}