C++로 행렬 속 검은 정사각형의 중심 좌표 찾기

문제 개요

n × m 크기의 행렬이 있다고 가정해 보겠습니다. 각 칸은 흰색('W') 또는 검은색('B')으로 표시되어 있습니다. 이 표 내부에는 한 변의 길이가 홀수인 정사각형 하나가 검은색으로 칠해져 있으며, 우리가 해야 할 일은 바로 이 정사각형의 중심 좌표를 찾는 것입니다.

예를 들어 입력이 다음과 같다고 해보죠.

이 경우 출력 결과는 (3, 1)이 됩니다.

해결 접근 방식

이 문제의 핵심 아이디어는 매우 간단합니다. 검은색으로 칠해진 정사각형의 한 변 길이가 항상 홀수이기 때문에, 모든 검은 칸('B')의 행 인덱스와 열 인덱스를 각각 더한 뒤 검은 칸의 총개수로 나누면 그 값이 곧 정사각형의 중심 좌표가 됩니다.

구체적인 풀이 단계는 다음과 같습니다.

• 행렬 전체를 순회하면서 'B'인 칸을 만날 때마다 개수(cnt)를 1 증가시키고, 해당 칸의 행 인덱스는 X에, 열 인덱스는 Y에 누적합니다.
• 순회가 끝나면 X와 Y를 각각 cnt로 나누어 평균값을 구합니다.
• (Y, X) 형태로 결과를 반환하거나 출력합니다.

n := 행렬의 행 개수
m := 행렬의 열 개수
cnt := 0
X := 0
Y := 0
for i := 0부터 n 미만까지 1씩 증가하며 반복:
    for j := 0부터 m 미만까지 1씩 증가하며 반복:
        if matrix[i, j] == 'B', then:
            cnt 1 증가
            X := X + i
            Y := Y + j
X := X / cnt
Y := Y / cnt
return (Y, X)

C++ 구현 예제

아래 코드를 통해 실제 구현 과정을 자세히 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<char>> matrix){
   int n = matrix.size();
   int m = matrix[0].size();
   int cnt = 0, X = 0, Y = 0;
   for (int i = 0; i < n; i++){
      for (int j = 0; j < m; j++)
         if (matrix[i][j] == 'B')
            cnt++, X += i, Y += j;
   }
   X /= cnt;
   Y /= cnt;
   printf("%d, %d\n", Y, X);
}
int main(){
   vector<vector<char>> matrix = { { 'W', 'W', 'B', 'B', 'B', 'W' },
      { 'W', 'W', 'B', 'B', 'B', 'W' }, { 'W', 'W', 'B', 'B', 'B', 'W' },
      { 'W', 'W', 'W', 'W', 'W', 'W' }, { 'W', 'W', 'W', 'W', 'W', 'W' } };
   solve(matrix);
}

입력

{ { 'W', 'W', 'B', 'B', 'B', 'W' },
   { 'W', 'W', 'B', 'B', 'B', 'W' }, { 'W', 'W', 'B', 'B', 'B', 'W' },
   { 'W', 'W', 'W', 'W', 'W', 'W' }, { 'W', 'W', 'W', 'W', 'W', 'W' } }

출력

3, 1

복잡도 분석

이 알고리즘은 행렬의 모든 칸을 한 번씩만 확인하므로 시간 복잡도는 O(n × m)입니다. 또한 추가적인 저장 공간 없이 몇 개의 변수만 사용하기 때문에 공간 복잡도는 O(1)로 매우 효율적입니다.