C++로 정사각형 보드에서 '승리 칸' 개수 구하기

문제 개요

n × n 크기의 정사각형 보드가 있다고 가정해 봅시다. 아말(Amal)과 비말(Bimal)은 게임을 진행하면서 나름의 규칙에 따라 보드의 각 칸에 숫자를 적어 나갑니다. 현재 보드에는 게임이 종료된 후의 숫자들이 남아 있습니다. 누가 승리했는지 판단하려면 승리 칸(winning square)의 개수를 계산해야 합니다.

특정 칸이 승리 칸인지 판단하는 방법은 다음과 같습니다.

1. 해당 칸과 같은 열(column)에 있는 모든 숫자의 합을 구합니다.
2. 같은 방식으로 해당 칸과 같은 행(row)에 있는 모든 숫자의 합을 구합니다.
3. 열의 합이 행의 합보다 엄격하게 크면 그 칸은 승리 칸입니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

이 경우 출력은 6입니다. 아래 표에서 색상으로 강조된 칸들이 바로 승리 칸입니다.

풀이 접근 방식

이 문제는 완전 탐색(brute force) 방식으로 해결할 수 있습니다. 보드의 모든 칸을 하나씩 확인하면서 각 칸이 속한 행의 합과 열의 합을 계산하고, 두 값을 비교하면 됩니다. 의사 코드(pseudo code)는 다음과 같습니다.

t := 0
n := size of M
for initialize i := 0, when i <= n - 1, update (increase i by 1), do:
   for initialize j := 0, when j <= n - 1, update (increase j by 1), do:
      s := 0
      l := 0
      for initialize k := 0, when k <= n - 1, update (increase k by 1), do:
         s := s + M[i, k]
         l := l + M[k, j]
      if l > s, then:
         (increase t by 1)
return t

여기서 변수 s는 i번째 행의 합, l은 j번째 열의 합을 의미합니다. 세 개의 중첩 반복문을 사용하므로 전체 시간 복잡도는 O(n³)입니다.

C++ 구현 예제

아래는 위 알고리즘을 실제로 구현한 C++ 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<vector<int>> M){
   int t = 0;
   int n = M.size();
   for (int i = 0; i <= n - 1; i++)
   for (int j = 0; j <= n - 1; j++){
      int s = 0;
      int l = 0;
      for (int k = 0; k <= n - 1; k++){
         s += M[i][k];
         l += M[k][j];
      }
      if (l > s)
         t++;
   }
   return t;
}
int main(){
   vector<vector<int>> matrix = { { 5, 7, 8, 4 }, { 9, 5, 3, 2 }, { 1, 6, 6, 4 }, { 9, 5, 7, 3 } };
   cout << solve(matrix) << endl;
}

입력

{ { 5, 7, 8, 4 }, { 9, 5, 3, 2 }, { 1, 6, 6, 4 }, { 9, 5, 7, 3 } }

출력

6