C++로 그리드에서 짝수 셀 개수를 최대화하는 연산 찾기

크기가 h × w인 그리드가 주어졌다고 가정해 보겠습니다. 그리드의 모든 셀에는 특정한 값이 할당되어 있으며, 우리의 목표는 짝수 값을 가진 셀의 개수를 최대화하는 것입니다.

이를 위해 다음과 같은 연산을 사용할 수 있습니다. 아직 선택하지 않은 셀 하나를 골라 해당 셀의 값을 1 감소시키고, 현재 셀과 세로 또는 가로로 인접한 다른 셀의 값을 1 증가시키는 방식입니다. 최종적으로 연산 횟수와 각 연산에 사용된 셀의 좌표를 출력해야 하며, 출력 형식은 다음과 같습니다.

• 연산 횟수

• 첫 번째 줄: (값이 감소된 셀 위치) - (값이 증가된 셀 위치)

  ...

• n번째 줄: (값이 감소된 셀 위치) - (값이 증가된 셀 위치)

예를 들어 입력이 h = 3, w = 3, grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}이라면 출력은 다음과 같습니다.

4
(0, 1) - (0, 2)
(2, 0) - (2, 1)
(2, 1) - (2, 2)
(0, 2) - (1, 2)

풀이 접근 방법

이 문제는 그리디(Greedy) 기법으로 해결할 수 있습니다. 각 행을 왼쪽에서 오른쪽으로 훑으면서 홀수 값을 만나면 오른쪽 인접 셀로 1을 넘겨 짝수로 만들고, 이후 마지막 열을 위에서 아래로 훑으며 같은 작업을 반복합니다. 이렇게 하면 마지막 셀 하나를 제외한 모든 셀을 짝수로 만들 수 있습니다. 해결 과정은 다음과 같습니다.

tuple을 저장하는 새 배열 result를 정의한다
i := 0으로 초기화하고, i < h인 동안 i를 1씩 증가시키며 반복:
    tp := 0
    j := 0으로 초기화하고, j < w인 동안 j를 1씩 증가시키며 반복:
        만약 tp > 0이면:
            result의 끝에 tuple(i, j - 1, i, j)를 삽입
            grid[i, j] := grid[i, j] + tp
        만약 grid[i, j] mod 2가 1이고 j < w-1이면:
            grid[i, j] := grid[i, j] - 1
            tp := 1
        그렇지 않으면
            tp := 0
tp := 0
i := 0으로 초기화하고, i < h인 동안 i를 1씩 증가시키며 반복:
    만약 tp > 0이면:
        result의 끝에 tuple(i - 1, w - 1, i, w - 1)를 삽입
    grid[i, w - 1] := grid[i, w - 1] + tp
    만약 grid[i, w - 1] mod 2가 1이면:
        grid[i, w - 1] := grid[i, w - 1] - 1
        tp := 1
    그렇지 않으면
        tp := 0
result의 크기를 출력한다
i := 0부터 result의 크기까지 반복하며 다음을 출력한다:
'(' + result[i]의 첫 번째 값 + ',' + result[i]의 두 번째 값 + ') - (' + result[i]의 세 번째 값 + ',' + result[i]의 네 번째 값 + ')'

예제 코드

아래 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;

void solve(int h, int w, vector<vector<int>>grid){
    vector<tuple<int,int,int,int>> result;
    for(int i = 0; i < h; i++){
        int tp = 0;
        for(int j = 0; j < w; j++){
            if(tp > 0){
                result.push_back(make_tuple(i, j-1, i, j));
                grid[i][j] += tp;
            }
            if(grid[i][j]%2 == 1 && j < w-1){
                grid[i][j] -= 1;
                tp = 1;
            }
            else
                tp = 0;
        }
    }
    int tp = 0;
    for(int i = 0; i < h; i++){
        if(tp > 0){
            result.push_back(make_tuple(i-1, w-1, i, w-1));
            grid[i][w-1] += tp;
        }
        if(grid[i][w-1]%2 == 1){
            grid[i][w-1] -= 1;
            tp = 1;
        }
        else
            tp = 0;
    }
    cout << (int)result.size() << endl;
    for(int i = 0; i < (int)result.size(); i++){
        cout << "(" << get<0>(result[i]) << ", " << get<1>(result[i])
        << ")" << " - (" << get<2>(result[i]) << ", " << get<3>(result[i]) << ")";
        cout << '\n';
    }
}
int main() {
    int h = 3, w = 3 ;
    vector<vector<int>> grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}};
    solve(h, w, grid);
    return 0;
}

입력

3, 3, {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}

출력

4
(0, 1) - (0, 2)
(2, 0) - (2, 1)
(2, 1) - (2, 2)
(0, 2) - (1, 2)

동작 원리 정리

위 알고리즘은 두 단계로 구성됩니다. 첫 번째 단계에서는 각 행을 순회하며 홀수 값을 가진 셀의 값 1을 오른쪽 인접 셀로 이동시켜, 마지막 열을 제외한 모든 셀을 짝수로 만듭니다. 두 번째 단계에서는 마지막 열을 위에서 아래로 순회하며 남은 홀수 값을 아래 셀로 넘깁니다. 그 결과 전체 그리드에서 최대 한 개의 셀(마지막 셀)만 홀수로 남게 되므로, 짝수 셀의 개수가 최대화됩니다. 시간 복잡도는 O(h × w)로 매우 효율적입니다.