Intuition

문제의 조건만 잘 생각하면서 푼다면 큰 어려움은 없다.
다만 구현량이 지금까지 경험했던 문제들에 비해서 조금 많다.

Approach 및 개선점

BFS vs DFS

블록 그룹들을 찾는 탐색 방식으로 BFS와 DFS를 떠올려 볼 수 있다.
둘 중 어느 방식을 쓰든 이 문제에서는 큰 차이가 없다. 나는 DFS를 썼다.

다만, 삼성 코딩테스트에서는 stack 메모리가 1MB로 제한되기 때문에 앞으로는 재귀함수 사용은 지양하는 것이 좋을 듯 하다.

void findGroup(int r, int c, int color) {
  for (int i = 0; i < 4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];

    if (nr >= 0 && nr < n && nc >= 0 && nc < n && game[nr][nc] != -1 &&
        visited[nr][nc] == 0 && game[nr][nc] <= m) {
      if (game[nr][nc] == 0 || game[nr][nc] == color) {
        ...
        visited[nr][nc] = 1;
        ...
        findGroup(nr, nc, color);
      }
    }
  }
}

이때, 무지개 블럭은 다른 그룹에서는 재방문이 가능하기 때문에 초기화를 시켜줬다.

int findMAX() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!visited[i][j] && game[i][j] != 0 && game[i][j] != -1 &&
          game[i][j] <= m) {
        visited[i][j] = 1;
        ...
        findGroup(i, j, game[i][j]);
        ...
        zero_cnt = 0;
        // 0은 재방문 가능
        for (int k = 0; k < zero_d_cnt; k++) visited[zero_r[k]][zero_c[k]] = 0;
      }
    }
  }
  return block_cnt_MAX * block_cnt_MAX;
}

좌표 저장

문제를 풀다보면 무지개블럭, 최대 블록그룹 등 블럭들의 좌표를 저장해야하는 상황이 생긴다.
N의 최댓값이 20이기 때문에 400짜리 크기의 배열을 2개 만들어서 row와 column을 각각 저장했다.

int group_MAX_r[400];
int group_MAX_c[400];
int number_of_group_MAX;

int group_MAX_r_tmp[400];
int group_MAX_c_tmp[400];
int group_MAX_tmp_idx;
...
        // 크기가 가장 큰 블록그룹의 좌표와 배열의 크기를 저장
        if ((block_cnt_MAX < block_cnt) ||
            (block_cnt_MAX == block_cnt && zero_cnt_MAX <= zero_cnt)) {
          block_cnt_MAX = block_cnt;
          zero_cnt_MAX = zero_cnt;
          number_of_group_MAX = group_MAX_tmp_idx;
          for (int k = 0; k < group_MAX_tmp_idx; k++) {
            group_MAX_r[k] = group_MAX_r_tmp[k];
            group_MAX_c[k] = group_MAX_c_tmp[k];
          }
        }

좀 더 편한 방법이 없을까 찾아보니 C++의 vector와 pair를 사용하는 방법이 있었다.

vector<pair<int, int>> var;

C++을 거의 안쓰다보니 STL을 잊어먹어서 생긴 문제다.

중력

열 하나를 위에서 아래로 순회하여 완전하게 마무리를 하고 다음 열로 넘어가는 방식으로 진행했다. stack에 무지개블럭과 일반블럭을 push했다가, -1이나 바닥에 도달하면 전부다 pop하며 위로 하나씩 채운다. -1이나 천장에 도달하기 전까지 위로 올라간다. stack이 빈 경우에는 m+1값으로 표시한다.

void gravity() {
  stack<int> blocks;

  for (int c = 0; c < n; c++) {
    for (int r = 0; r < n; r++) {
      if (game[r][c] >= 0 && game[r][c] <= m) blocks.push(game[r][c]);

      if (r + 1 == n || game[r + 1][c] == -1) {
        // 현재 칸부터 채워야함
        for (int i = r; i >= 0 && game[i][c] != -1; i--) {
          if (!blocks.empty()) {
            game[i][c] = blocks.top();
            blocks.pop();
          } else
            game[i][c] = m + 1;
        }
      }
    }
  }
}

마찬가지로 stack memory가 1MB로 한정되기 때문에, 앞으로는 stack을 전역변수로 할당하거나 stack을 사용하지 않고 처리하는 것이 좋겠다.

회전

회전은 좌표를 비교해보면 행과 열간의 규칙을 발견할 수 있다.

void rotate() {
  int game_tmp[20][20];
  for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 20; j++) {
      game_tmp[i][j] = game[i][j];
    }
  }

  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      game[r][c] = game_tmp[c][n - 1 - r];
    }
  }
}

극한까지 메모리가 제한된다면 in-place 방식으로도 처리를 하는 방법이 있다.

Solution

#include <stdio.h>

#include <stack>

using namespace std;

int game[20][20];
int visited[20][20];

int zero_d_cnt;
int zero_r[400];
int zero_c[400];

int group_MAX_r[400];
int group_MAX_c[400];
int number_of_group_MAX;

int group_MAX_r_tmp[400];
int group_MAX_c_tmp[400];
int group_MAX_tmp_idx;

int n, m;
int score, block_cnt_MAX, zero_cnt, zero_cnt_MAX;
int block_cnt = 1;

int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void findGroup(int r, int c, int color);
int findMAX();
void gravity();
void rotate();

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", &game[i][j]);
      if (game[i][j] == 0) {
        zero_r[zero_d_cnt] = i;
        zero_c[zero_d_cnt++] = j;
      }
    }
  }

  int score_tmp;
  while ((score_tmp = findMAX()) > 1) {
    score += score_tmp;

    // 저장된 좌표 통해서 최대블록그룹 지우기
    for (int i = 0; i < number_of_group_MAX; i++)
      game[group_MAX_r[i]][group_MAX_c[i]] = m + 1;

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

    // 0개수 및 위치 재확인
    zero_d_cnt = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (game[i][j] == 0) {
          zero_r[zero_d_cnt] = i;
          zero_c[zero_d_cnt++] = j;
        }
      }
    }
    // init
    block_cnt_MAX = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        visited[i][j] = 0;
      }
    }
  }

  printf("%d\n", score);
  return 0;
}

void findGroup(int r, int c, int color) {
  for (int i = 0; i < 4; i++) {
    int nr = r + dr[i];
    int nc = c + dc[i];

    if (nr >= 0 && nr < n && nc >= 0 && nc < n && game[nr][nc] != -1 &&
        visited[nr][nc] == 0 && game[nr][nc] <= m) {
      if (game[nr][nc] == 0 || game[nr][nc] == color) {
        if (game[nr][nc] == 0) zero_cnt++;
        visited[nr][nc] = 1;
        block_cnt++;
        group_MAX_r_tmp[group_MAX_tmp_idx] = nr;
        group_MAX_c_tmp[group_MAX_tmp_idx++] = nc;
        findGroup(nr, nc, color);
      }
    }
  }
}

int findMAX() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (!visited[i][j] && game[i][j] != 0 && game[i][j] != -1 &&
          game[i][j] <= m) {
        visited[i][j] = 1;
        group_MAX_r_tmp[group_MAX_tmp_idx] = i;
        group_MAX_c_tmp[group_MAX_tmp_idx++] = j;
        findGroup(i, j, game[i][j]);

        // 크기가 가장 큰 블록그룹의 좌표와 배열의 크기를 저장
        if ((block_cnt_MAX < block_cnt) ||
            (block_cnt_MAX == block_cnt && zero_cnt_MAX <= zero_cnt)) {
          block_cnt_MAX = block_cnt;
          zero_cnt_MAX = zero_cnt;
          number_of_group_MAX = group_MAX_tmp_idx;
          for (int k = 0; k < group_MAX_tmp_idx; k++) {
            group_MAX_r[k] = group_MAX_r_tmp[k];
            group_MAX_c[k] = group_MAX_c_tmp[k];
          }
        }

        // init
        group_MAX_tmp_idx = 0;
        block_cnt = 1;
        zero_cnt = 0;
        // 0은 재방문 가능
        for (int k = 0; k < zero_d_cnt; k++) visited[zero_r[k]][zero_c[k]] = 0;
      }
    }
  }
  return block_cnt_MAX * block_cnt_MAX;
}

void gravity() {
  stack<int> blocks;

  for (int c = 0; c < n; c++) {
    for (int r = 0; r < n; r++) {
      if (game[r][c] >= 0 && game[r][c] <= m) blocks.push(game[r][c]);

      if (r + 1 == n || game[r + 1][c] == -1) {
        // 현재 칸부터 채워야함
        for (int i = r; i >= 0 && game[i][c] != -1; i--) {
          if (!blocks.empty()) {
            game[i][c] = blocks.top();
            blocks.pop();
          } else
            game[i][c] = m + 1;
        }
      }
    }
  }
}

void rotate() {
  int game_tmp[20][20];
  for (int i = 0; i < 20; i++) {
    for (int j = 0; j < 20; j++) {
      game_tmp[i][j] = game[i][j];
    }
  }

  for (int r = 0; r < n; r++) {
    for (int c = 0; c < n; c++) {
      game[r][c] = game_tmp[c][n - 1 - r];
    }
  }
}

지적 및 질문 환영