알고리즘 > 백트래킹A > 영역 구하기(1457)

Question

문제 링크

Solving

* 어려웠던 점

좌표가 (0,0)~(5,7)로 주어져서 배열을 어떻게 채워넣어야 할지에 대한 혼란이 왔다.

결국 영역의 크기를 받을 때, 채워질 영역을 계산하여 map[0][0]을 2로 채웠다. 

        

1 2 3 4 5 6 7 8 9

for (int i0 = (세로1 + 1); i0 <= 세로2; i0++)         {             for (int j = (가로1 + 1); j <= 가로2; j++)             {                 if (map[i0][j] == 2)                     continue;                 map[i0][j] = 2;             }         }

위의 그림과 같이 라벨링한 다음부터는 편하게 문제를 풀 수 있었다.

이와 비슷한 고민으로 고생을 했던 문제로 koi_ladder ☜ 링크 클릭 

가 있었다.

Code

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106

#include <stdio.h> #pragma warning(disable:4996) int m, n, k, a, b, c, d; int map[105][105];   int cnt_num; // 영역 개수 저장 int size[10001], cnt_size; // 영역 크기 저장, 영역 사이즈   int x[] = { 0, 1, 0, -1 }; int y[] = { -1, 0, 1, 0 };   void algo(int posy, int posx);   int main() {     FILE *fin = fopen("input.txt", "rt");     FILE *fout = fopen("output.txt", "wt");       fscanf(fin, "%d %d %d", &m, &n, &k);     for (int i = 1; i <= m; i++)         for (int j = 1; j <= n; j++)             map[i][j] = 1;     for (int i = 1; i <= k; i++)     {         fscanf(fin, "%d %d %d %d", &a, &b, &c, &d);         // 바로 영역 채우기         for (int i0 = b+1; i0 <= d; i0++)         {             for (int j = a+1; j <= c; j++)             {                 if (map[i0][j] == 2)                     continue;                 map[i0][j] = 2;             }         }     }          // test print     /*for (int i = 0; i <= m + 1; i++)     {         for (int j = 0; j <= n + 1; j++)         {             printf("%2d ", map[i][j]);         }         printf("\n");     }*/       for (int i = 1; i <= m; i++)     {         for (int j = 1; j <= n; j++)         {             if (map[i][j] == 1)             {                 cnt_num++;                 cnt_size = 0;                 algo(i, j);                 size[cnt_num] = cnt_size;                   // test print                 /*printf("\n");                 for (int i = 0; i <= m + 1; i++)                 {                     for (int j = 0; j <= n + 1; j++)                     {                         printf("%2d ", map[i][j]);                     }                     printf("\n");                 }                 printf("현재까지 영역 개수는 %d 영역%d의 넓이는 %d",cnt_num, cnt_num,size[cnt_num] );                 printf("\n");*/             }         }     }     // bubble sort     for (int i = 1; i <= cnt_num; i++)     {         for (int j = 1; j <= cnt_num - i; j++)         {             if (size[j] > size[j+1])             {                 int tmp = size[j];                 size[j] = size[j + 1];                 size[j + 1] = tmp;             }         }     }       // print     fprintf(fout, "%d\n", cnt_num);     for (int i = 1; i <= cnt_num; i++)         fprintf(fout, "%d ", size[i]);     fprintf(fout, "\n"); }   void algo(int posy, int posx) {     map[posy][posx] = 2; // 갔다는 표시     cnt_size++;     for (int i = 0; i < 4; i++)     {                 if (map[posy + y[i]][posx + x[i]] == 2 || map[posy + y[i]][posx + x[i]] == 0)             continue;                 else if (map[posy + y[i]][posx + x[i]] == 1)              algo(posy + y[i], posx + x[i]);     } }