백준 (DFS) 2667번 - 단지번호붙이기

2667-단지번호붙이기 acmicpc.net/problem/2667

해당 문제는 DFS 기초문제이다.

DFS를 사용한 이후에 나온 값들에 대한 정렬이 필요하다.

나는 처음에 퀵정렬 사용하려고 qsort함수를 사용하기 위해서 int compare(const void* a, const void* b) 함수를 새로 만들어서 사용하기도 했는데

왜인지 잘 모르겠지만 정렬이 잘 안됬음.

그래서 그냥 버블정령 만들어서 바로 사용했음.

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

int map[100][100];
int visit[100][100];
int* result;
int stack=0;
int n;
int max=0;

void dfs(int i, int j)
{
   int x, y,k;
   int dx[] = {0,1,0,-1};
   int dy[] = {1,0,-1,0};

   visit[i][j] = 1;
   
   max++;


   for(k=0; k<4; k++)
   {
      x=i+dx[k];
      y=j+dy[k];
      if(x<0 || y<0 || x>n-1 || y>n-1)
         continue;
      if(visit[x][y] == 0 && map[i][j] == map[x][y])
      {
         dfs(x, y);
      }
   }
}

int main(void)
{
   int i, j;
   char input[100];
   int temp;
   
   scanf("%d", &n);
   fflush(stdin);

   result = (int*)malloc(sizeof(int)*n*n);
   memset(map, 0, sizeof(map));
   memset(visit, 0, sizeof(visit));
   memset(result, 0, sizeof(result));

   for(i=0; i<n; i++)
   {
      scanf("%s", input);
      fflush(stdin);
      for(j=0; j<n; j++)
      {
         map[i][j] = input[j]-48;
      }
   }

   for(i=0; i<n; i++)
   {
      for(j=0; j<n; j++)
      {
         if(visit[i][j] == 0 && map[i][j] == 1)
         {
            max=0;
            dfs(i, j);   
            result[stack++] = max;
         }
      }
   }
   
   for(i=0; i<stack-1; i++)
   {
	   for(j=0; j<stack-1; j++)
	   {
		   if(result[j] > result[j+1])
		   {
			   temp = result[j];
			   result[j] = result[j+1];
			   result[j+1] = temp;
		   }
	   }
   }

   printf("%d\n", stack);
   for(i=0; i<stack; i++)
   {
      printf("%d\n", result[i]);
   }
   return 0;
}