1247 최적 경로

회사 출발 엔 명의 고객 방문 후 자신의 집으로 돌아감

회사, 집, 고객 위치, 이차원 정수로 주어짐

두 위치 사이 거리 절대값으로 계산됨

회사 출발 엔 명의 고객 모두 방문 후 집으로 돌아오는 경로 중 갖아 짧은 것을 찾으시오.

 

회사와 집의 좌표가 주어지고, 2~10명 사이의 고객 좌표가 주어짐.

 

회사에서 출발해서 모두 방문하고 집에 돌아가는 경로 중 총 이동거리가 가장 짧은 경로를 찾는 프로그램을 작성

 

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

멀티 쓰레드 환경일 경우 sync 값이 true일 때는 Thread safe 라서 예상치 못한 값이 나오지 않지만, false를 시킬 경우 Thread unsafe 해지기 때문에 예상치 못한 값이 나타날 수 있음.

 

#include <iostream> // 헤더파일
#include <memory.h> 
#include <algorithm>

using namespace std;
struct point { // 포인트 구조체 만들어서
    int x;
    int y;
};

int dist[12][12]; //
int dp[12][1 << 11]; // 디피 사용해서 저장함, 고객의 수가 최대 10명이므로 시작점, 끝점 포함 12
int check, N;
point node[12]; // 

int solve(int curr_p, int visit); // 현재 위치와 방문 한 곳?

int main()
{
    freopen("input.txt", "r", stdin);
    cin.tie(NULL); ios::sync_with_stdio(false); // 싱크 막음, 속도 상승
    int T, res; // 테케, 결과값

    cin >> T; // 테케 받음


    for (int t = 1; t <= T; t++) {
        memset(dp, 0, sizeof(dp)); // 디피 배열 초기화
        cin >> N; // 고객의 수
        cin >> node[0].x >> node[0].y; // 시작점
        cin >> node[N + 1].x >> node[N + 1].y; // 끝점

        check = (1 << (N + 1)) - 1; 
        for (int n = 1; n < N + 1; n++) {
            cin >> node[n].x >> node[n].y;
        }
        for (int n = 0; n < N + 2; n++)
            for (int m = 0; m < N + 2; m++)
                dist[n][m] = abs(node[n].x - node[m].x) + abs(node[n].y - node[m].y); // dist 를 계싼해서 저장해둠
        res = solve(0, 1);

        cout << "#" << t << " " << res << "\n";

    }
    return 0;
}
int solve(int curr_p, int visit) // 현재 위치? 에서 visit
{
    int &res = dp[curr_p][visit];
    if (dp[curr_p][visit] != 0)
        return res;
    if (visit == check)
        return dist[curr_p][N + 1];
    res = 987654321;
    for (int n = 1; n < N + 1; n++) {
        if (visit&(1 << n)) continue;
        res = min(res, solve(n, visit | (1 << n)) + dist[curr_p][n]);
    }

    return res;
}