C++로 행렬에서 주변에 가장 많은 별(*)을 가진 알파벳 찾기

별(*)과 알파벳으로 채워진 행렬 M이 있다고 가정해 봅시다. 이때 각 알파벳을 둘러싸고 있는 별의 개수를 세어, 가장 많은 별을 가진 알파벳을 찾아야 합니다.

예를 들어 다음과 같은 행렬이 있다고 하겠습니다.

위 행렬에서 알파벳 A와 C는 각각 주변에 7개의 별을 가지고 있으며, 이것이 최대값입니다. 두 글자가 동일한 개수일 경우에는 사전순(lexicographic order)으로 더 앞선 문자가 출력되어야 하므로, 이 예제의 정답은 A가 됩니다.

해결 접근 방식

풀이 방법은 매우 간단합니다.

1. 행렬을 순회하면서 알파벳 문자를 찾습니다.
2. 알파벳을 발견하면 해당 위치를 기준으로 상하좌우 및 대각선까지 포함한 8방향의 인접 칸을 확인하여 별(*)의 개수를 셉니다.
3. 각 알파벳과 그 주변 별 개수를 unordered_map(해시 맵)에 저장합니다.
4. 맵을 순회하면서 별 개수가 가장 큰 값을 찾고, 개수가 같다면 사전순으로 더 작은 문자를 선택합니다.

C++ 구현 예제

#include <iostream>
#include<unordered_map>
#define MAX 4
using namespace std;
int checkStarCount(int mat[][MAX], int i, int j, int n) {
   int count = 0;
   int move_row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
   int move_col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
   for (int k = 0; k < 8; k++) {
      int x = i + move_row[k];
      int y = j + move_col[k];
      if (x >= 0 && x < n && y >= 0 && y < n && mat[x][y] == '*')
      count++;
   }
   return count;
}
char charWithMaxStar(int mat[][4], int n) {
   unordered_map<char, int> star_count_map;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if ((mat[i][j] - 'A') >= 0 && (mat[i][j] - 'A') < 26) {
            int stars = checkStarCount(mat, i, j, n);
            star_count_map[mat[i][j]] = stars;
         }
      }
   }
   int max = -1;
   char result = 'Z' + 1;
   for (auto x : star_count_map) {
      if (x.second > max || (x.second == max && x.first < result)) {
         max = x.second;
         result = x.first;
      }
   }
   return result;
}
int main() {
   int mat[][4] = {
      { 'B', '*', '*', '*' },
      { '*', '*', 'C', '*' },
      { '*', 'A', '*', '*' },
      { '*', '*', '*', 'D' }
   };
   int n = 4;
   cout << charWithMaxStar(mat, n) << " has maximum amount of stars around it";
}

실행 결과

A has maximum amount of stars around it

코드 설명

checkStarCount 함수는 현재 위치 (i, j)를 기준으로 8방향 이동 배열(move_row, move_col)을 사용해 인접한 칸들을 검사합니다. 이때 행렬 범위를 벗어나지 않도록 경계 조건(x >= 0 && x < n 등)을 반드시 확인해야 하며, 인접 칸이 별(*)이면 카운트를 증가시킵니다.

charWithMaxStar 함수는 전체 행렬을 이중 반복문으로 순회하면서, 문자가 대문자 알파벳(A~Z)인지 판별합니다. 알파벳이라면 checkStarCount를 호출해 주변 별 개수를 구하고 해시 맵에 저장합니다. 마지막으로 맵을 순회하며 별 개수가 최대인 문자를 찾는데, 개수가 동일한 경우에는 사전순으로 앞서는 문자를 우선 선택하는 조건(x.first < result)이 포함되어 있습니다.

이 알고리즘의 시간 복잡도는 O(n² × 8), 즉 O(n²)이며, 추가로 사용되는 공간은 알파벳 종류만큼의 해시 맵 공간이므로 O(26) 수준으로 효율적입니다.