21W37-구현 - 07 그래프의 최소 비용 문제

[moodmine]

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

그 전 이슈들 주차들을 잘못 쓴 게 좀 있어서 수정해야함

[happy-oh]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<string.h>
#include<cmath>
#define MAX_VALUE 10000
using namespace std;
int T_depth;
long long x_data[1001];
long long y_data[1001];
int check_data[1001];
long long key[1001];
int py[1001]; // in this problem,, py is not needed
long long sum;
double sum_mul_rate;
double rate;
int the_next_idx;

void Calc(int n)
{
    int count, idx, jdx, kdx, mdx, ndx;
    long long find_min = 1000000000001;
    long long temp;
    sum = 0;

    key[0] = 0;
    check_data[0] = 1;

    for (idx = 1; idx < n; ++idx)
    {
        key[idx] = (x_data[idx] - x_data[0]) * (x_data[idx] - x_data[0]) + (y_data[idx] - y_data[0]) * (y_data[idx] - y_data[0]);
        py[idx] = 0;
        if (find_min > key[idx]) {
            the_next_idx = idx;
            find_min = key[idx];
        }
    }
    check_data[the_next_idx] = 1;

    for (count = 1; count <= n-2; ++count)
    {
        find_min = 1000000000001;
        for (idx = 1; idx < n; ++idx)
        {

            if (!check_data[idx])
            {
                temp = (x_data[idx] - x_data[the_next_idx]) * (x_data[idx] - x_data[the_next_idx]) + (y_data[idx] - y_data[the_next_idx]) * (y_data[idx] - y_data[the_next_idx]);
                if (temp < key[idx])
                {
                    key[idx] = temp;
                    py[idx] = the_next_idx;
                }

            }
        }
        for (idx = 1; idx < n; ++idx)
        {

            if (!check_data[idx])
            {
                if (find_min > key[idx]) {
                    find_min = key[idx];
                    the_next_idx = idx;
                }
            }
        }
        check_data[the_next_idx] = 1;
    }

    for (idx = 0; idx < n; ++idx)
    {
        sum = sum + key[idx];
    }

    return ;

}

int main(void)
{

    freopen("input.txt", "r", stdin);
    int T, N, test_case;

    int answer_value;
    scanf("%d", &T);
    int idx, jdx, kdx, mdx, ndx;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &N);
        for (idx = 0; idx < N; ++idx)
        {
            scanf("%lld", &x_data[idx]);
        }
        for (idx = 0; idx < N; ++idx)
        {
            scanf("%lld", &y_data[idx]);
        }
        scanf("%lf", &rate);

        for (idx = 0; idx <= 1000; ++idx)
        {
            key[idx] = 1000000000001;
            py[idx] = -1;
            check_data[idx] = 0;
        }

        Calc(N);
        sum_mul_rate = sum * rate;

        printf("#%d ", test_case);
        printf("%.0lf\n", round(sum_mul_rate));

        /*printf("testcast : %d\n", test_case);

        for (idx = 0; idx < N; ++idx)
        {
            printf("%d %d\n", x_data[idx], y_data[idx]);
        }
        printf("rate : %f\n", rate);
        // */ 

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

[murry2018]

SWEA 1251. 하나로

#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>

using namespace std;

// union-find
vector<int> root(1000);
vector<int> level(1000);

int find(int i) {
  while (root[i] != i)
    i = root[i];
  return i;
}

void merge(int i, int j) {
  int x = find(i);
  int y = find(j);
  if (x != y) {
    if (level[x] > level[y]) {
      // x is larger
      root[y] = x;
    } else {
      // y is larger or equal
      root[x] = y;
      if (level[x] == level[y]) {
        level[y]++;
      }
    }
  }
}

void init_uf(int n) {
  root.resize(n);
  level.resize(n);
  for (int i = 0; i < n; i++) {
    root[i] = i;
    level[i] = 1;
  }
}

// utiility
vector<int> read_ints(int n) {
  vector<int> s(n); // RVO
  for (int i = 0; i < n; i++) {
    int t;
    scanf("%d", &t);
    s[i] = t;
  }
  return s;
}

double square(double x) {
  return x * x;
}

double square_length(int x1, int x2, int y1, int y2) {
  return square(x1 - x2) + square(y1 - y2);
}

// kruscal
struct edge {
  int s, e;
  double sqlen;
  bool operator<(edge &rhs) {
    return sqlen < rhs.sqlen;
  }
};

bool compare(edge e, edge f) {
  return e.sqlen < f.sqlen;
}

int N; double E;
double solve(const vector<int> &xs, const vector<int> &ys) {
  vector<edge> es(N);
  // setup graph
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      edge e = { i, j, square_length(xs[i], xs[j], ys[i], ys[j]) };
      es.push_back(e);
    }
  }
  sort(es.begin(), es.end(), &compare);
  // find mst
  double total = 0;
  for (edge &e : es) {
    if (find(e.s) != find(e.e)) { // has no cycle
      merge(e.s, e.e);
      total += E*e.sqlen;
    }
  }
  return total;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    scanf("%d", &N);
    vector<int> xs = read_ints(N);
    vector<int> ys = read_ints(N);
    scanf("%lf", &E);
    init_uf(N);
    long long cost = round(solve(xs, ys));
    printf("#%d %lld\n", t, cost);
  }
}

[moodmine]

SWEA 1251. 하나로

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

#define INF 2000000000001;
long long int tmp;
long long int tmp2;
long long int island[1000][2];
long long int table[1000][3];
// table[num][0] : key, table[num][1] : pi, table[num][2] : visit

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 = 0;
        scanf("%d", &num);
        for (int i = 0; i < num; i++)
        {
            scanf("%lld", &island[i][0]);
        }
        for (int i = 0; i < num; i++)
        {
            scanf("%lld", &island[i][1]);
        }
        double E;
        scanf("%lf", &E);

        for (int i = 0; i < num; i++)
        {
            table[i][0] = INF;
            table[i][1] = -1;
            table[i][2] = 0;
        }

        table[0][0] = 0;
        table[0][1] = 0;

        int value;
        int signal;

        for (int i = 0; i < num; i++)
        {
            tmp = INF;
            for (int j = 0; j < num; j++)
            {
                if (!table[j][2] && table[j][0] < tmp)
                {
                    tmp = table[j][0];
                    value = j;
                }
            }
            table[value][2] = 1;

            for (int j = 0; j < num; j++)
            {
                if (table[j][2])
                    continue;
                tmp = ((island[value][0] - island[j][0]) * (island[value][0] - island[j][0]))
                    + ((island[value][1] - island[j][1]) * (island[value][1] - island[j][1]));

                if (tmp < table[j][0])
                {
                    table[j][0] = tmp;
                    table[j][1] = value;
                }
            }
        }
        double result = 0;
        for (int i = 0; i < num; i++)
            result += table[i][0];
        printf("%.0lf\n", E * result);
    }
    return 0;
}