[알고리즘] 1. [C/C++] 4방향 체인코드를 이용한 논 크기 측정 문제

알고리즘 문제 공부를 하고 있는데,


정리하여 공부겸 포스팅 할려 합니다.


'논 그룹묶기 문제' 이며,


0은 논이아니고 1은 논입니다.

2차원 배열 nxn으로 구성되어있으며,


test.txt의

첫 줄에는 테스트 케이스 숫자

다음 줄 부터는 nxn의 배열 크기 , 배열 값 순으로 되어있는 것을 읽으면 됩니다.

이 후 체인코드로 그룹핑된 갯수와

각 그룹들의 크기를 출력하는 문제입니다.

ChainCode를 구현하는 문제로서, 4방향이지만, 여기서 대각선만 추가하면

8방향 체인코드 또한 구성됩니다.


test.txt는 '알고리즘 자료' 카테고리의 첫번째에 답과 함께 올려 놓았습니다.






다음은 구현 코드이며, 알고리즘으로는,


모든 배열 인덱스에 접근하지만, 이미 그룹화 된 값과 0은 제외를 하고,


방문 할 때마다 그룹 값을 넣고,

그룹화가 끝나면, GroupNum을 증가시켜, 다시 시작하는 방법입니다.

값을 얻을 수 있습니다.

일종의 완전 탐색이지만, 예외조건이 있기에, 모든 곳을 탐색하진 않습니다.

아래 코드에서, 대각선 조건만 추가한다면, 8방향 체인코드로 구성됩니다.

#include 
#include 
using namespace std;


class NoN{
public:
 int size;
};

NoN InitialNoN(int size)
{
 NoN mData;
 mData.size = size;
 return mData;
}
bool IsOutBoard(int arrSize, int y, int x)
{
 if (y < 0 || x < 0 || y >= arrSize || x >= arrSize)
  return true;
 
 return false;
}

bool IsZeroOrGroupCheck(int y, int x, int **board)
{
 if (board[y][x] != 1) return true;

 return false;
}

int Lableling(int arrSize,int **board,int y,int x,int group)
{
 if (IsOutBoard(arrSize,y,x)) return 0;
 
 if (IsZeroOrGroupCheck(y,x,board)) return 0;

 board[y][x] = group;
 int result = 1;
 int t1 = Lableling(arrSize, board, y + 1, x, group); // Down
 int t2 = Lableling(arrSize, board, y - 1, x, group); // Up
 int t3 = Lableling(arrSize, board, y, x + 1, group); // Right
 int t4 = Lableling(arrSize, board, y, x - 1, group); // Left

 return result + t1 + t2 + t3 + t4;
}

void InitialBoard(int arrSize, int** board)
{
 for (int i = 0; i < arrSize; i++)
 {
  for (int j = 0; j < arrSize; j++)
  {
   board[i][j] = 0;
  }
 }
}
int** SetBoard(int arrSize)
{
 int ** board = new int*[arrSize];
 for (int i = 0; i < arrSize; i++)
  board[i] = new int[arrSize];
 
 InitialBoard(arrSize, board);
 return board;
}
void AllDeleteBoard(int **board,int arrSize)
{
 for (int i = 0; i < arrSize; i++)
  delete board[i];
}
int _tmain(int argc, _TCHAR* argv[])
{
 FILE *fp = fopen("test.txt", "rt");
 if (fp == NULL)
 {
  cout << "FILE OPEN ERROR" << endl; 
  return 0;
 }

 int T = 0;
 fscanf(fp, "%d\n", &T);

 for (int i = 0; i < T; i++)
 {
  vector mData;
  int group = 2;
  int arrSize = 0;
  fscanf(fp, "%d\n", &arrSize);
  int ** board = SetBoard(arrSize);

  char temp;
  for (int j = 0; j < arrSize; j++)
   for (int k = 0; k < arrSize; k++)
    fscanf(fp, "%d%c", &board[j][k], &temp);

   for (int j = 0; j < arrSize; j++){
    for (int k = 0; k < arrSize; k++){
     if (IsZeroOrGroupCheck(j, k, board)) continue;

     int check = Lableling(arrSize, board, j, k, group);
     mData.push_back(InitialNoN(check));
     group++;
    }
   }

   cout << "#" << i + 1 << " : " << mData.size();
   for (int vec = 0; vec < mData.size(); vec++)
    cout << " " << mData[vec].size << " ";

   cout << endl;
   AllDeleteBoard(board, arrSize);
 }



 return 0;
}

추가로 읽으면 좋을 것