21W30-구현 - 05 백트래킹

[moodmine]

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3Fvw66AAYBBARB

[moodmine]

SWEA 1247. 최적경로

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

int now_best;

void FindTempWay(int** arr_customer, int* visit, int num_customer)
{
    int* local_visit = new int[num_customer + 2];
    for (int i = 0; i < num_customer + 2; i++)
    {
        local_visit[i] = visit[i];
    }
    int current = 0;
    int remain_num_customer = num_customer;
    int shortest_way = -1;
    int way = 0;
    int temp_i = -1;
    while (remain_num_customer > 0)
    {
        shortest_way = -1;
        for (int i = 0; i < num_customer + 2; i++)
        {
            if (i == 1)
                continue;
            if (local_visit[i] == 0)
            {
                if (shortest_way == -1)
                {
                    shortest_way = abs(arr_customer[i][0] - arr_customer[current][0]) + abs(arr_customer[i][1] - arr_customer[current][1]);
                    temp_i = i;
                }
                else
                {
                    way = abs(arr_customer[i][0] - arr_customer[current][0]) + abs(arr_customer[i][1] - arr_customer[current][1]);
                    if (way < shortest_way)
                    {
                        shortest_way = way;
                        temp_i = i;
                    }
                }
            }
        }
        local_visit[temp_i] = 1;
        now_best += shortest_way;
        current = temp_i;
        remain_num_customer--;
    }
    now_best += abs(arr_customer[1][0] - arr_customer[current][0]) + abs(arr_customer[1][1] - arr_customer[current][1]);
}

int FindWay(int** arr_customer, int* visit, int current, int num_remain_customer, int num_customer, int distance)
{
    int shortest_distance = 0;
    int local_distance = -1;
    int temp_distance = -1;
    int result_distance = -1;
    int* local_visit = new int[num_customer + 2];
    for (int i = 0; i < num_customer + 2; i++)
    {
        local_visit[i] = visit[i];
    }
    if (num_remain_customer < 1)
    {
        local_distance = distance + abs(arr_customer[1][0] - arr_customer[current][0]) + abs(arr_customer[1][1] - arr_customer[current][1]);
        return local_distance;
    }
    else
    {
        for (int i = 2; i < num_customer + 2; i++)
        {
            if (local_visit[i] == 0)
            {
                local_visit[i] = 1;
                local_distance = distance + abs(arr_customer[i][0] - arr_customer[current][0]) + abs(arr_customer[i][1] - arr_customer[current][1]);

                if (local_distance > now_best)
                    continue;

                if (result_distance == -1)
                    result_distance = FindWay(arr_customer, local_visit, i, num_remain_customer - 1, num_customer, local_distance);
                else
                    temp_distance = FindWay(arr_customer, local_visit, i, num_remain_customer - 1, num_customer, local_distance);

                local_visit[i] = 0;

                if (temp_distance != -1)
                {
                    if (temp_distance < result_distance)
                    {
                        result_distance = temp_distance;
                    }
                }
            }
        }
    }
    delete[]local_visit;
    return result_distance;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; ++test_case)
    {
        printf("#%d ", test_case);
        int num_customer = 0;
        scanf("%d", &num_customer);
        int** arr = new int* [num_customer + 2];
        int* visit = new int[num_customer + 2];
        // 회사, 집, 고객 1, 고객 2, ... , 고객 n의 방문 여부
        for (int i = 0; i < num_customer + 2; i++)
        {
            arr[i] = new int[2];
            visit[i] = 0;
        }
        for (int i = 0; i < num_customer + 2; i++)
        {
            scanf("%d %d", &arr[i][0], &arr[i][1]);
        }
        visit[0] = 1; // 회사 출근

        int result = 0;
        now_best = 0;
        FindTempWay(arr, visit, num_customer);
        result = FindWay(arr, visit, 0, num_customer, num_customer, 0);
        printf("%d\n", result);
        for (int i = 0; i < num_customer; i++)
        {
            delete[]arr[i];
        }
        delete[]visit;
    }
    return 0;
}

[murry2018]

SWEA 1247. 최적경로

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct pos {
    int x, y;
    pos() {}
    pos(int x, int y) : x(x), y(y) {}
};

static int n_customers;
static vector<pos> customers;
static vector<int> visit_order;
static pos source;
static pos destination;
static int best_distance;
static vector<int> best_order;

void init() {
    // n_customer, source sould be set first.
    visit_order.clear();
    visit_order.resize(n_customers+1, -1);
    visit_order[n_customers] = 0;
    customers.clear();
    customers.resize(n_customers+1, source);
    customers.push_back(source);
    best_distance = 1e9;
    best_order.clear();
    best_order.resize(n_customers+1, -1);
    // customers, destination should be set.
}

int compute_distance(pos p, pos q) {
    return abs(p.x - q.x) + abs(p.y - q.y);
}

void find_path(const int customer_id, const int distance, const int index) {
    int nothing = true;
    if (distance > best_distance)
        return ;
    for (int i = 0; i < n_customers; i++) {
        if (visit_order[i] == -1) {
            nothing = false;
            const int distance_next =
                compute_distance(customers[customer_id], customers[i]);
            visit_order[i] = index+1;
            find_path(i, distance + distance_next, index+1);
            visit_order[i] = -1;
        }
    }
    if (nothing) {
        const int dist_home = distance +
            compute_distance(customers[customer_id], destination);
        if (best_distance > dist_home) {
            best_distance = dist_home;
            for (int i = 0; i < n_customers; i++) {
                best_order[i] = visit_order[i];
            }
        }
    }
}

int main() {
    int nT;
    cin >> nT;
    for (int T = 1; T <= nT; T++) {
        cin >> n_customers;
        cin >> source.x >> source.y;
        cin >> destination.x >> destination.y;
        init();
        for (int i = 0; i < n_customers; i++) {
            cin >> customers[i].x >> customers[i].y;
        }
        find_path(n_customers, 0, 0);
        cout << '#' << T << ' ' << best_distance << '\n';
    }
}

수도코드

고객 숫자 = 정수
고객 목록 = [좌표], '고객 숫자' + 1만큼
고객 목록[고객 숫자] = 출발 지점(회사)
방문 순서 = [정수], '고객 숫자' 만큼, 초기값 -1
목적지(집) = 좌표
최단 거리 = 정수
최단 방문 순서 = [정수], '고객 숫자' 만큼, 초기값 -1

고객번호, 현재 거리, 순서에 대한 경로 탐색 = {
  전부 방문 := 참
  현재 거리 > 최단 거리 이라면:
    돌아가기
  다음고객 = 0부터 고객 숫자 아래까지 반복:
    다음 고객을 방문 안한 경우, 즉 방문 순서[다음 고객] == -1이면:
      전부 방문 := 거짓
      방문 순서[다음 고객] = 순서+1
      다음 거리 = (현재 거리 +
          현재 위치, 즉 고객 목록[고객번호]와 다음 고객 사이의 거리)
      다음 고객, 다음 거리, 순서+1에 대한 경로 탐색
      방문 순서[다음 고객] = -1
  전부 방문했고, 최단거리 > 현재 거리 + (현재 위치와 집 사이의 거리) 이라면:
    최단거리 = 현재 거리 + (현재 위치와 집 사이의 거리)
    최단 경로에 현재 경로를 복사
}

[happy-oh]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<string.h>

using namespace std;
int T_depth;
int input_data[10][3];
int start[3];
int endpos[3];
int smallest;

int cal_dis(int x_1, int y_1, int x_2, int y_2)
{
    int x_dis = x_1 - x_2;
    int y_dis = y_1 - y_2;
    if (x_dis < 0)
        x_dis *= -1;
    if (y_dis < 0)
        y_dis *= -1;
    int total_dis = x_dis + y_dis;
    return total_dis;
}
int cal_all(int cu_depth, int adding_dis, int added_idx)
{
    int add_temp = 0;
    int idx;
    if (T_depth == cu_depth)
    {
        adding_dis += cal_dis(endpos[0], endpos[1], input_data[added_idx][0], input_data[added_idx][1]);
        if (adding_dis < smallest)
            smallest = adding_dis;
        return(0);
    }
    else
    {
        for (idx = 0; idx < T_depth; ++idx)
        {
            if ((input_data[idx][2] == 0) && (!(added_idx == idx)))
            {
                if (cu_depth == 0)
                {
                    add_temp = cal_dis(start[0], start[1], input_data[idx][0], input_data[idx][1]);
                    adding_dis += add_temp;
                    input_data[idx][2] = 1;
                    cal_all(cu_depth + 1, adding_dis, idx);
                    input_data[idx][2] = 0;
                    adding_dis -= add_temp;
                }
                else
                {
                    add_temp = cal_dis(input_data[added_idx][0], input_data[added_idx][1], input_data[idx][0], input_data[idx][1]);
                    adding_dis += add_temp;
                    input_data[idx][2] = 1;
                    cal_all(cu_depth + 1, adding_dis, idx);
                    input_data[idx][2] = 0;
                    adding_dis -= add_temp;
                }
            }
        }
    }
}

int main(void)
{
    freopen("input.txt", "r", stdin);
    int T, test_case;
    scanf("%d", &T);
    int idx, jdx, kdx, mdx, ndx;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        smallest = 10000;
        scanf("%d", &T_depth);
        scanf("%d %d ", &endpos[0], &endpos[1]);
        scanf("%d %d ", &start[0], &start[1]);

        for (idx = 0; idx < T_depth; ++idx)
        {
            scanf("%d %d ", &input_data[idx][0], &input_data[idx][1]);
        }
        for (idx = 0; idx < 10; ++idx)
        {
            input_data[idx][2] = 0;
        }
        cal_all(0, 0, -1);
        printf("#%d %d\n", test_case, smallest);
        //printf("\n%d", T_depth);
        //printf("\n%d %d ", endpos[0], endpos[1]);
        //printf("\n%d %d ", start[0], start[1]);
        //for (idx = 0; idx < T_depth; ++idx)
        //{
        //    printf("%d %d ", input_data[idx][0], input_data[idx][1]);
        //}
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}