BOJ[백준] - 2569 - 짐정리

https://www.acmicpc.net/problem/2569

 

(1) Graph로 해결하려 했는데 정렬하기 전과 정렬하고 후에 자리가 똑같은 정점(vertex)을 빼고 나머지 정점들 가지고만 MST(최소신장트리)를

만들어 볼까? 하는 생각을 했었습니다.

4 2 1 3 을 입력 받으면 정렬 했을 때, 1 2 3 4 이고 2는 그대로 있으면 되는 것이죠..

따라서 cyclic 정점 set이 (2)와 (1, 3, 4)로 분리되니  (1, 3, 4) 로만 가지고 MST를 구성해 봤습니다.

이 그림 처럼. 총 합이 9가 나오지 뭡니까 ?? 

이대로 끝인줄 알았습니다 ㅎ..

 

 

 

 

(2) 1 8 9 7 6 을 입력으로 받으면,  정렬 후 1 6 7 8 9 가 되고,  1은 그 자리에 있으면 되니..  (1)과 (6, 7, 8, 9)로 분리를 해서 앞서 적용한 것처럼

계산을 했더니 !??  (6+7) + (6+8) + (6+9) = 42 가 나왔습니다.

BUT!! 저 경우엔 정답이 41이네요...

1 8 9 7 6 -> 6 8 9 7 1 (1+6) -> 6 8 1 7 9 (1+9) -> 6 8 7 1 9 (1+7) -> 6 1 7 8 9 (1+8) ->

 1 6 7 8 9 (1+6) = 41 입니다.

 case 2번은 생각을 못하고 있었는데 결국 뛰어난 PS블로거님에게서 힌트를 얻었습니다. 

 

#include <cstdio>
 
#define MIN(a,b)  ((a)<(b) ? (a):(b))
typedef struct vertex
{
   int data, index;
} V;
 
const int MXN = 1000;
V a[MXN + 1];
char chk[MXN + 1];
 
void swap(V *v1, V *v2)
{
   V t = *v1;
   *v1 = *v2, *v2 = t;
}
 
int main()
{
   int n;
   scanf("%d", &n);
   for(int i = 0; i < n; i++)
   {
      scanf("%d", &a[i].data);
      a[i].index = i;
   }
 
   // bubble sort in ascending order of a[].data
   for (int i = 0; i < n - 1; i++)
      for (int j = 0; j < n - i - 1; j++)
         if (a[j].data > a[j + 1].data)
            swap(&a[j], &a[j + 1]);
 
   long long ans = 0;
   for(int i = 0; i < n; i++)
   {
      if(chk[i])
         continue;
      int cycle = 0;
      // loop 1 cycle, cycle = the # of vertices in a cycle
      for(int j = i; !chk[j]; j = a[j].index)
      {
         cycle++;
         ans += a[j].data;
         chk[j]++;
      }
      // case 1 : check only non-sorted cyclic vertices
      //          4 2 1 3 -> check (1,3,4) -> (1+3) + (1+4) = 9
      // case 2 : check a vertex having minimum value in the graph and non-sorted cyclic vertices
      //          1 8 9 7 6 -> check (1) and (8,9,7,6) -> (1+6) + (1+9) + (1+7) + (1+8) + (1+6) = 41
      ans += MIN( (cycle-2) * a[i].data , a[i].data + (cycle+1) * a[0].data );
   }
   printf("%lld", ans);
   return 0;
}