[C++ / 3085] 사탕 게임

문제

3085번: 사탕 게임

---

문제 설명

봄보니 (Bomboni) 게임.

N x N 크기의 랜덤한 사탕으로 채워져있는 판이 있다.

사탕 색이 다른 인접두 칸을 고른 뒤, 두 칸의 사탕을 교환한다.

마지막으로, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

 

(뭐, 대충 옛날 애니팡 같은 게임 규칙.)

---

풀이 방식

이 문제는 brute force 방식 즉, 모든 방법을 다 탐색해야 한다.

 

1. 우선 (i, j)와 (i, j+1)의 위치를 바꾼다.

2. 그 다음엔 모든 row에 대해서 조사를 한다.

만약 같은 문자가 연속으로 나타난다면, count의 값을 증가시키고 문자가 다르다면 count는 1로 유지한다.

3. 위와 같은 작업을 col에 대해서도 동일하게 진행한다.

4. (j, i)와 (j + 1, i)에 대해서도 동일한 2,3과 동일한 작업을 해야하므로 1에서 바꿔두었던 위치를 원래대로 돌린다.

5. (j, i)와 (j + 1, i)에 대해서 1~4와 동일한 작업을 한다.

---

솔루션

#include <iostream>
#include <algorithm>

using namespace std;

int maxCount = 0;

void searchRow(char map[51][51], int n)
{
  for (int i = 0; i < n; i++)
  {
    int count = 1;
    for (int j = 0; j < n; j++)
    {
      if (map[i][j] == map[i][j + 1])
      {
        count++;
      }
      else
      {
        if (count > maxCount)
        {
          maxCount = count;
        }
        count = 1;
      }
    }
  }
}

void searchCol(char map[51][51], int n)
{
  for (int i = 0; i < n; i++)
  {
    int count = 1;
    for (int j = 0; j < n; j++)
    {
      if (map[j][i] == map[j + 1][i])
      {
        count++;
      }
      else
      {
        if (count > maxCount)
        {
          maxCount = count;
        }
        count = 1;
      }
    }
  }
}

int main()
{
  int n;
  cin >> n;

  char map[51][51];

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      cin >> map[i][j];
    }
  }

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      swap(map[i][j], map[i][j + 1]);
      searchRow(map, n);
      searchCol(map, n);

      swap(map[i][j], map[i][j + 1]);
      // 원상태 복귀
      swap(map[j][i], map[j + 1][i]);
      searchRow(map, n);
      searchCol(map, n);

      swap(map[j][i], map[j + 1][i]);
    }
  }

  cout << maxCount << endl;
}

---

알게된 점

C++의 algorithm의 라이브러리에는 다음과 같은 알고리즘을 제공하고 있다. 자세한 내용은 아래를 참고

[C++ 표준] STL 알고리즘