그리드에서 청소 로봇이 청소할 수 있는 최대 셀 수를 구하는 C++ 프로그램

문제 개요

h × w 크기의 격자(grid) 위에서 동작하는 청소 로봇을 만든다고 가정해 보겠습니다. 청소가 필요한 더러운 셀은 총 m개이며, 정수 쌍(pair)으로 이루어진 배열 dirt에 각 셀의 좌표가 담겨 있습니다.

이 청소 로봇은 특정 셀에 배치되면 해당 행(row)과 열(column)에 속한 모든 셀을 한 번에 청소할 수 있습니다. 따라서 우리의 과제는 로봇을 어디에 배치해야 가장 많은 더러운 셀을 청소할 수 있는지 판단하고, 청소 가능한 최대 셀 개수를 구해 출력하는 것입니다.

입력 예시와 기대 결과

예를 들어 h = 3, w = 3, m = 3이고 dirt = {{0, 0}, {1, 1}, {2, 1}}라고 가정해 보겠습니다. 이때 출력값은 3입니다. 로봇을 셀 {1, 0}에 배치하면 해당 행과 열을 모두 커버하게 되어 격자 안의 세 개의 더러운 셀을 전부 청소할 수 있기 때문입니다.

문제 해결 접근 방법

핵심 아이디어는 간단합니다. 더러운 셀이 가장 많이 몰려 있는 행과 열을 각각 찾아, 로봇을 그 교차점에 배치하는 것입니다. 다만 한 가지 주의할 점이 있습니다. 최적 행과 최적 열의 교차 지점 자체가 더러운 셀이라면 두 카운트의 합에서 1을 빼야 합니다(같은 셀이 중복해서 계산되기 때문입니다). 알고리즘은 다음과 같이 진행됩니다.

맵 하나를 선언한다
크기가 100인 두 배열 hcount와 wcount를 선언하고 0으로 초기화한다
maxh = 0, maxw = 0, res = 0으로 초기화한다
두 배열 p, q를 선언한다
i := 0부터 i < m까지 반복(i는 1씩 증가):
    a := dirt[i]의 첫 번째 값
    b := dirt[i]의 두 번째 값
    pairMap[(a, b)] := 1
    hcount[a]를 1 증가
    wcount[b]를 1 증가
i := 0부터 i < h까지 반복(i는 1씩 증가):
    maxh := maxh와 hcount[i] 중 큰 값
i := 0부터 i < w까지 반복(i는 1씩 증가):
    maxw := maxw와 wcount[i] 중 큰 값
i := 0부터 i < h까지 반복(i는 1씩 증가):
    만약 hcount[i]가 maxh와 같다면:
        p의 끝에 i를 삽입
i := 0부터 i < w까지 반복(i는 1씩 증가):
    만약 wcount[i]가 maxw와 같다면:
        q의 끝에 i를 삽입
p의 각 원소 i에 대해:
    q의 각 원소 j에 대해:
        만약 pairMap[(i, j)]가 0이 아니라면:
            res := maxh + maxw - 1
        그렇지 않으면:
            res := maxh + maxw
            res를 반환
res를 반환

C++ 구현 예제

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int solve(int h, int w, int m, vector<pair<int, int>> dirt){
    map<pair<int, int>, int> pairMap;
    int hcount[100] = {0}, wcount[100] = {0}, maxh = 0, maxw = 0, res = 0;
    vector<int>p, q;
    for (int i = 0; i < m; i++) {
        int a = dirt[i].first;
        int b = dirt[i].second;
        pairMap[make_pair(a, b)] = 1;
        hcount[a]++;
        wcount[b]++;
    }
    for (int i = 0; i < h; i++)
        maxh = max(maxh, hcount[i]);
    for (int i = 0; i < w; i++)
        maxw = max(maxw, wcount[i]);
    for (int i = 0; i < h; i++){
        if (hcount[i] == maxh)
            p.push_back(i);
    }
    for (int i = 0; i < w; i++) {
        if (wcount[i] == maxw)
            q.push_back(i);
    }
    for (auto i : p) {
        for (auto j : q) {
            if (pairMap[make_pair(i, j)])
                res = maxh + maxw - 1;
            else {
                res = maxh + maxw;
                return res;
            }
        }
    }
    return res;
}
int main() {
    int h = 3, w = 3, m = 3;
    vector<pair<int, int>> dirt = {{0, 0}, {1, 1}, {2, 1}};
    cout<< solve(h, w, m, dirt);
    return 0;
}

입력

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

출력

3

복잡도 분석

시간 복잡도: 더러운 셀을 순회하는 데 O(m), 각 행과 열의 최댓값을 찾는 데 O(h + w), 마지막으로 후보 교차점을 검사하는 데 O(p × q)(p, q는 각각 최대 오염 수를 가진 행과 열의 개수)가 소요됩니다.

공간 복잡도: 더러운 셀 좌표를 저장하는 맵에 O(m)이 필요하며, 행·열별 카운트 배열은 고정 크기로 사용됩니다.