#include <iostream>
#include <cstring> // memset
#include <utility> // pair
#include <vector> // 그룹 정보 저장
#include <queue> // BFS

using namespace std;

int N, M; // 격자의 크기, 색상의 개수
int A[21][21]; // 검은색 블록은 -1, 무지개 블록은 0
bool visited[21][21] = {false}; // 방문체크

struct GROUP {
  int x, y; // 시작정보
  int rainbow = 0; // 무지개 블록 수
  vector<pair<int, int> > xy; // 그룹 블록 좌표 - 구조체에 vector 넣기 가능
};

vector<GROUP> v; // 그룹정보 저장 벡터

int ans = 0;

// 인접 칸 구하기
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct SEARCH{
 int y, x;
 int color;
};

queue<SEARCH> q; // BFS

// 블록 그룹 찾기
void BFS(int y, int x, int color){
  q.push({y, x, color});
  visited[y][x] = true;

  GROUP g; // BFS로 탐색한 그룹 정보 저장
  g.x = x; g.y = y;
  g.xy.push_back({y, x});

  while(!q.empty()){
    int y = q.front().y;
    int x = q.front().x;
    q.pop();

    for(int i = 0; i < 4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];

      // 범위 벗어나는 경우
      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }

      // 일반 블록 또는 무지개 블록이 블록 집합으로 묶일 수 있음.
      // 일반 블록의 색은 모두 같아야 한다
      if(!visited[ny][nx] && (A[ny][nx] == 0 || A[ny][nx] == color)){
        visited[ny][nx] = true;
        g.xy.push_back({ny, nx});

        if(A[ny][nx] == 0){
          g.rainbow++;
        }
        q.push({ny, nx, color});
      }
    }
  }

  // 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며
  if(g.xy.size() >= 2){
    v.push_back(g); // 모든 그룹 블록들 정보 저장
  }
}

void gravity(){
  // 아랫쪽 블록부터 아래로 내려줘야함
  // 제일 아래있는 칸의 블록은 내려줄 필요 없음
  // 열
  for(int i = N-2; i >= 0; i--){
    // 행
    for(int j = 0; j < N; j++){
      // 빈공간이거나 검정 블록인 경우 무시
      if(A[i][j] == -2 || A[i][j] == -1){
        continue;
      }
      
      int downY = i; // (j, i)의 아랫칸 y의 좌표
      while(1){
        downY++; // 다음 아랫칸 탐색

        // 제일 아랫칸까지 갔으면
        if(downY == N){
          break;
        }
        // 아랫칸이 비어있지 않으면
        if(A[downY][j] != -2){
          break;
        }
      }
      swap(A[--downY][j], A[i][j]); // 중력으로 블록 내려주기
    }
  }
}

// 맵 90도 반시계 방향  
void rotate(){
  int temp[21][21] = {0};

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      temp[N - j - 1][i] = A[i][j]; // 반시계방향 저장
    }
  }

  memcpy(A, temp, sizeof(A));
}

int main(){
  scanf("%d %d", &N, &M);
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      scanf("%2d", &A[i][j]);
    }
  }
  
  // 오토플레이 끝까지 계속 - 블록 그룹이 존재하는 동안 계속해서 반복
  while(1){
    memset(visited, false, sizeof(visited)); // 방문 초기화
    v.clear(); // 블록 그룹 정보 초기화

    // 크기가 가장 큰 블록 그룹을 찾는다
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        // 블록 그룹에는 일반 블록이 하나 이상 포함되어야하기에 일반 블록에서 블록 그룹 탐색 시작
        if(!visited[i][j] && A[i][j] > 0){
          BFS(i, j, A[i][j]);
        }
        
        // 무지개 visit 초기화해야함. 모든 경우에 대해서 그룹지을 수 있기 때문
        for(int n = 0; n < N; n++){
          for(int m = 0; m < N; m++){
            if(A[n][m] == 0){
              visited[n][m] = false;
            }
          }
        }
      }
    }

    // 블록 그룹 존재 x
    if(v.size() == 0){
      break;
    }

    // 크기가 가장 큰 블록 그룹을 찾는다.
    int maxGroup = 0;
    int maxGroupIdx = 0;
    for(int i = 0; i < v.size(); i++){
      if(v[i].xy.size() > maxGroup){
        maxGroup = v[i].xy.size();
        maxGroupIdx = i;
      } else if(v[i].xy.size() == maxGroup){
        // 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
        if(v[i].rainbow > v[maxGroupIdx].rainbow){
          maxGroup = v[i].xy.size();
          maxGroupIdx = i;
        } else if(v[i].rainbow == v[maxGroupIdx].rainbow){
          // 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을
          // 문제는 행과 열을 혼동해서 사용하고 있다. 
          // 중력이 작용하면 모든 블록이 행의 번호가 큰 칸으로 이동 -> 행이 y인 것을 알 수 있다.
          if(v[i].y > v[maxGroupIdx].y){
            maxGroup = v[i].xy.size();
            maxGroupIdx = i;
          } else if(v[i].y == v[maxGroupIdx].y){
            // 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
            if(v[i].x > v[maxGroupIdx].x){
              maxGroup = v[i].xy.size();
              maxGroupIdx = i;
            }
          }
        }
      }
    }

    // 블록 그룹의 모든 블록을 제거
    for(int i = 0; i < v[maxGroupIdx].xy.size(); i++){
      int x = v[maxGroupIdx].xy[i].second;
      int y = v[maxGroupIdx].xy[i].first;

      A[y][x] = -2;
    }

    // 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B^2점을 획득
    int B = v[maxGroupIdx].xy.size(); // 블록 그룹에 포함된 블록의 수를 B
    ans += B * B;

    // 격자에 중력
    gravity();

    // 격자가 90도 반시계 방향으로 회전
    rotate();

    // 격자에 중력
    gravity();
  }

  printf("%d", ans);

  return 0;
}

아 꽤 헤맸다. 진짜 반례 만드는게 너무 어려움...
맨날 반례 검색해서 보고 그제서야 오류 수정하기 일쑤다.

이제 풀이를 좀 자세히 써보려고

문제 풀이

1. 문제 파악

• 블록 그룹은 연결된 블록의 집합 : BFS를 사용해서 탐색

|r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸 :

// 인접 칸 구하기
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

좌표 배열 사용해서 for문 돌아 인접 칸 구하기

• 블록 그룹에 대한 디테일한 정보가 필요함. 시작 좌표, 블록들의 좌표, 무지개 블록의 수를 저장해야함
  <이유>
  시작 좌표 :
  블록 그룹이 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
  블록들의 좌표 :
  블록 집합을 만들고 제일 큰 블록 집합을 탐색 -> 가장 큰 블록 집합의 정보를 재탐색하면 비효율적
  그래서 처음부터 아예 탐색하면서 좌표값들을 저장시키는 것이 좋음.
  그리고 블록들의 좌표 집합의 크기가 블록 집합의 크기가 되기 때문에 계산하기가 편함.
  무지개 블록 수 :
  블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹을 택해야하기 때문에

struct GROUP {
  int x, y; // 시작정보
  int rainbow = 0; // 무지개 블록 수
  vector<pair<int, int> > xy; // 그룹 블록 좌표 - 구조체에 vector 넣기 가능
};

그래서 이런 구조체를 만들어 BFS 탐색에 사용하게 되었다.

2. main 문

// 크기가 가장 큰 블록 그룹을 찾는다
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        // 블록 그룹에는 일반 블록이 하나 이상 포함되어야하기에 일반 블록에서 블록 그룹 탐색 시작
        if(!visited[i][j] && A[i][j] > 0){
          BFS(i, j, A[i][j]);
        }
        
        // 무지개 visit 초기화해야함. 모든 경우에 대해서 그룹지을 수 있기 때문
        for(int n = 0; n < N; n++){
          for(int m = 0; m < N; m++){
            if(A[n][m] == 0){
              visited[n][m] = false;
            }
          }
        }
      }
    }

블록 그룹을 찾기 위해 맵을 돌아가며 BFS 탐색을 시작한다.
블록 그룹에는 일반 블록이 하나 이상 포함되어야하기 때문에 일반 블록부터 블록 그룹 탐색을 시작하면 된다.
이렇게 하면 따로 모두 무지개 블록인 경우를 따로 탐색하지 않아도 된다.

주의

바보같이 무지개 블록은 다른 블록들도 블록 집합에 포함시킬 수 있다
= 무지개 블록은 방문 여부를 계속 초기화 해줘야한다.
라는 사실을 잊었음 주의하기...ㅜㅜ

3. BFS

void BFS(int y, int x, int color){
  q.push({y, x, color});
  visited[y][x] = true;

  GROUP g; // BFS로 탐색한 그룹 정보 저장
  g.x = x; g.y = y;
  g.xy.push_back({y, x});

그냥 방문 여부 체크해주고 BFS가 다 돌아가면 블록 그룹 하나를 찾은 것이기 때문에
그것을 체크해주기 위한 변수 g를 만들어 시작 지점을 체크해주고

while(!q.empty()){
    int y = q.front().y;
    int x = q.front().x;
    q.pop();

    for(int i = 0; i < 4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];

      // 범위 벗어나는 경우
      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }

      // 일반 블록 또는 무지개 블록이 블록 집합으로 묶일 수 있음.
      // 일반 블록의 색은 모두 같아야 한다
      if(!visited[ny][nx] && (A[ny][nx] == 0 || A[ny][nx] == color)){
        visited[ny][nx] = true;
        g.xy.push_back({ny, nx});

        if(A[ny][nx] == 0){
          g.rainbow++;
        }
        q.push({ny, nx, color});
      }
    }
  }

계속 반복문 돌면서 방문여부 체크해가며 블록 그룹을 찾아주면 된다.
블록 그룹을 찾게되면 그룹 정보에 해당 좌표를 저장하고, 무지개 블록의 경우 무지개 블록의 개수도 세어준다.

주의

일반 블록의 색은 모두 같아야하므로 색 정보를 같이 큐에 담아서 탐색을 해준다.

// 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며
  if(g.xy.size() >= 2){
    v.push_back(g); // 모든 그룹 블록들 정보 저장
  }

주의

블록의 수가 2개 이상인 경우에만 블록 그룹이 된다.
때문에 그 경우를 체크해 블록 집합을 저장하는 벡터에 값을 넣어주면 된다.

3. main 문

// 블록 그룹 존재 x
    if(v.size() == 0){
      break;
    }

오토 플레이는 블록 그룹이 존재하는 동안 계속 반복되기에
존재하지 않는 경우에는 break 해줌

// 크기가 가장 큰 블록 그룹을 찾는다.
    int maxGroup = 0;
    int maxGroupIdx = 0;
    for(int i = 0; i < v.size(); i++){
      if(v[i].xy.size() > maxGroup){
        maxGroup = v[i].xy.size();
        maxGroupIdx = i;
      } else if(v[i].xy.size() == maxGroup){
        // 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 
        if(v[i].rainbow > v[maxGroupIdx].rainbow){
          maxGroup = v[i].xy.size();
          maxGroupIdx = i;
        } else if(v[i].rainbow == v[maxGroupIdx].rainbow){
          // 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을
          // 문제는 행과 열을 혼동해서 사용하고 있다. 
          // 중력이 작용하면 모든 블록이 행의 번호가 큰 칸으로 이동 -> 행이 y인 것을 알 수 있다.
          if(v[i].y > v[maxGroupIdx].y){
            maxGroup = v[i].xy.size();
            maxGroupIdx = i;
          } else if(v[i].y == v[maxGroupIdx].y){
            // 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
            if(v[i].x > v[maxGroupIdx].x){
              maxGroup = v[i].xy.size();
              maxGroupIdx = i;
            }
          }
        }
      }
    }

크기가 가장 큰 블록 그룹을 찾는다.
우선 무조건 크기가 큰 것을 찾고.
크기가 같으면 -> 무지개 블록 수가 가장 많은 블록 그룹 -> 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.

주의

문제에서 우리가 통념적으로 생각하는 행과 열이 반대다. y가 행이고 x가 열이다.
때문에 이걸 조심해서 하기...
헷갈려서 잘못 체크 했었는데
중력이 작용하면 모든 블록이 행의 번호가 큰 칸으로 이동이라는 문장을 보고 행이 y인 것을 알 수 있었다.
완전 독해 문제 아냐??

4. gravity

void gravity(){
  // 아랫쪽 블록부터 아래로 내려줘야함
  // 제일 아래있는 칸의 블록은 내려줄 필요 없음
  // 열
  for(int i = N-2; i >= 0; i--){
    // 행
    for(int j = 0; j < N; j++){
      // 빈공간이거나 검정 블록인 경우 무시
      if(A[i][j] == -2 || A[i][j] == -1){
        continue;
      }
      
      int downY = i; // (j, i)의 아랫칸 y의 좌표
      while(1){
        downY++; // 다음 아랫칸 탐색

        // 제일 아랫칸까지 갔으면
        if(downY == N){
          break;
        }
        // 아랫칸이 비어있지 않으면
        if(A[downY][j] != -2){
          break;
        }
      }
      swap(A[--downY][j], A[i][j]); // 중력으로 블록 내려주기
    }
  }
}

이런 중력 문제는 풀어보는게 처음이라 인터넷을 참고해서 풀었다.
중력이 작용하므로 열이 큰 아래에 있는 블록들부터 탐색하면서 내려주는 것이 옳다.
내려줌을 탐색할 일반 블록을 찾게 되면
새로운 인덱스를 사용하여 아랫칸이 비어있는지, 또는 범위를 벗어났는지를 체크해서 위치를 바꿔준다.

5. rotate

// 맵 90도 반시계 방향  
void rotate(){
  int temp[21][21] = {0};

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      temp[N - j - 1][i] = A[i][j]; // 반시계방향 저장
    }
  }

  memcpy(A, temp, sizeof(A));
}

이렇게 반시계 방향으로 도는 것은 그냥 외워버리는 게 편한 것 같다.
마법사 상어와 파이어스톰 문제에서도 써뒀는데

시계 방향 : (i, j) => (j, n - i - 1)

반시계방향 : (i, j) => (n - j - 1, i)

x축 대칭 : (i, j) => (n - i - 1, j)

y축 대칭 : (i, j) => (i, n - j - 1)

점대칭 : (i, j) => (n - i - 1, n - j - 1)

아무튼 대충 중요한 건 다 설명 쓴 듯...

주석 없는 코드

#include <iostream>
#include <cstring>
#include <utility>
#include <vector>
#include <queue>

using namespace std;

int N, M;
int A[21][21];
bool visited[21][21] = {false};

struct GROUP {
  int x, y;
  int rainbow = 0;
  vector<pair<int, int> > xy;
};

vector<GROUP> v;

int ans = 0;

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct SEARCH{
 int y, x;
 int color;
};

queue<SEARCH> q;

void BFS(int y, int x, int color){
  q.push({y, x, color});
  visited[y][x] = true;

  GROUP g;
  g.x = x; g.y = y;
  g.xy.push_back({y, x});

  while(!q.empty()){
    int y = q.front().y;
    int x = q.front().x;
    q.pop();

    for(int i = 0; i < 4; i++){
      int nx = x + dx[i];
      int ny = y + dy[i];

      if(nx < 0 || ny < 0 || nx >= N || ny >= N){
        continue;
      }

      if(!visited[ny][nx] && (A[ny][nx] == 0 || A[ny][nx] == color)){
        visited[ny][nx] = true;
        g.xy.push_back({ny, nx});

        if(A[ny][nx] == 0){
          g.rainbow++;
        }
        q.push({ny, nx, color});
      }
    }
  }

  if(g.xy.size() >= 2){
    v.push_back(g);
  }
}

void gravity(){
  for(int i = N-2; i >= 0; i--){
    for(int j = 0; j < N; j++){
      if(A[i][j] == -2 || A[i][j] == -1){
        continue;
      }
      
      int downY = i;
      while(1){
        downY++;

        if(downY == N){
          break;
        }
        if(A[downY][j] != -2){
          break;
        }
      }
      swap(A[--downY][j], A[i][j]);
    }
  }
}

void rotate(){
  int temp[21][21] = {0};

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      temp[N - j - 1][i] = A[i][j];
    }
  }

  memcpy(A, temp, sizeof(A));
}

int main(){
  scanf("%d %d", &N, &M);
  
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      scanf("%2d", &A[i][j]);
    }
  }
  
  while(1){
    memset(visited, false, sizeof(visited));
    v.clear();

    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
        if(!visited[i][j] && A[i][j] > 0){
          BFS(i, j, A[i][j]);
        }
        
        for(int n = 0; n < N; n++){
          for(int m = 0; m < N; m++){
            if(A[n][m] == 0){
              visited[n][m] = false;
            }
          }
        }
      }
    }

    if(v.size() == 0){
      break;
    }

    int maxGroup = 0;
    int maxGroupIdx = 0;
    for(int i = 0; i < v.size(); i++){
      if(v[i].xy.size() > maxGroup){
        maxGroup = v[i].xy.size();
        maxGroupIdx = i;
      } else if(v[i].xy.size() == maxGroup){
        if(v[i].rainbow > v[maxGroupIdx].rainbow){
          maxGroup = v[i].xy.size();
          maxGroupIdx = i;
        } else if(v[i].rainbow == v[maxGroupIdx].rainbow){
          if(v[i].y > v[maxGroupIdx].y){
            maxGroup = v[i].xy.size();
            maxGroupIdx = i;
          } else if(v[i].y == v[maxGroupIdx].y){
            if(v[i].x > v[maxGroupIdx].x){
              maxGroup = v[i].xy.size();
              maxGroupIdx = i;
            }
          }
        }
      }
    }

    for(int i = 0; i < v[maxGroupIdx].xy.size(); i++){
      int x = v[maxGroupIdx].xy[i].second;
      int y = v[maxGroupIdx].xy[i].first;

      A[y][x] = -2;
    }

    int B = v[maxGroupIdx].xy.size();
    ans += B * B;

    gravity();
    rotate();
    gravity();
  }

  printf("%d", ans);

  return 0;
}