K사 : 같은 색깔의 블록 갯수 구하기 (Flood Fill)(Recursive) [C,C++]

K사의 17년도 1번 문제이다.

문제를 한 마디로 말하면

'가장 많은 그룹을 가진 색의 그룹 개수와 최대 색칠 개수를 세라' 인데

이해하기 어려우시죠?

그림으로 보여드리겠습니다.

여기서 가장 많은 그룹을 가진 색은 빨간색입니다.

그룹의 개수는 4개입니다.

최대 색칠 개수는 오른쪽 위에 있는 43개입니다.

이해가 가시나요?

재귀 알고리즘 중 하나인 Flood Fill 알고리즘을 이용해 푸는 문제입니다.

계속 방문하여 개수를 체크 후에 더 체크할 게 없다면 return하는 방식입니다.

색깔을 찾는 코드만 짤 수 있으면 이 문제도 풀 수 있기 때문에

저는 하얀 배경에서 검은 색깔을 찾는 코드를 만들었습니다.

여러 색깔을 담는 배열 하나만 만들어주면 바로 바꿀 수 있는 문제입니다.

void MoveDirection(vector<vector<int>> &picture, int row, int column, int count)
{
 picture[row][column] = -1;
 
 count++;
 if (count > MaxCount)
  MaxCount = count;
 
 if (column < picture[0].size() - 1)
 {
  if (picture[row][column + 1] > 0) // RIGHT
   MoveDirection(picture, row, column + 1, count);
 }
 if (column > 0)
 {
  if (picture[row ][column - 1] > 0) // LEFT
   MoveDirection(picture, row, column - 1, count);
 }
 if (row > 0)
 {
  if (picture[row - 1][column] > 0) // UP
   MoveDirection(picture, row - 1, column, count);
 }
 if (row < picture.size() - 1)
 {
  if (picture[row + 1][column] > 0) // DOWN
   MoveDirection(picture, row + 1, column, count);
 }
}

vector<int> solution(vector<vector<int>> &picture)
{
 for (int iIndex = 0; iIndex < picture.size(); iIndex++)
 {
  for (int jIndex = 0; jIndex < picture[0].size(); jIndex++)
  {
   if (picture[iIndex][jIndex] > 0)
   {
    MoveDirection(picture, iIndex, jIndex, 0);
    PartCount++;
   }
  }
 }

 vector<int> answer = { PartCount, MaxCount };
 return answer;
}

<검정색의 그룹 개수와 최대 색칠 개수를 찾는 코드>