모양 만들기 16932

문제

접근 방법

영역을 구분 지어 놓고 영역에 해당하는 크기를 저장해 두면 해당 영역에 도달할 시 전부 탐색할 필요 없이 어떤 영역인지 확인하면 된다.
DFS든 BFS든 상관없기에 편한 방법으로 구현하면 될 것이고 나는 BFS가 더 편해서 BFS로 접근했다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> pii;
int N, M, dy[] = {1, -1, 0, 0}, dx[] = {0, 0, 1, -1}, ret = 0, idx = 0;
vector<vector<int>> map, group;
vector<int> groupSum;
void bfs(int y, int x)
{
    int sum = 1;
    group[y][x] = idx;
    queue<pii> q;
    q.push({y, x});
    while (!q.empty())
    {
        pii cur = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i)
        {
            pii next = {cur.first + dy[i], cur.second + dx[i]};
            if (next.first < 0 || next.second < 0 || next.first >= N || next.second >= M ||
                !map[next.first][next.second] || group[next.first][next.second] != -1)
                continue;
            group[next.first][next.second] = idx;
            ++sum;
            q.push(next);
        }
    }
    groupSum.push_back(sum);
    ++idx;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    map = group = vector<vector<int>>(N, vector<int>(M, -1));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> map[i][j];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            if (map[i][j])
            {
                if (group[i][j] == -1)
                    bfs(i, j);
            }
            else
            {
                int sum = 1;
                set<int> s;
                for (int k = 0; k < 4; ++k)
                {
                    int ny = i + dy[k], nx = j + dx[k];
                    if (ny < 0 || nx < 0 || ny >= N || nx >= M || !map[ny][nx] || s.find(group[ny][nx]) != s.end())
                        continue;
                    if (group[ny][nx] == -1)
                        bfs(ny, nx);
                    s.insert(group[ny][nx]);
                    sum += groupSum[group[ny][nx]];
                }
                ret = max(ret, sum);
            }
        }
    cout << ret;
    return 0;
}

풀이

같은 영역을 다른 영역으로 착각하고 합해주면 중복되기에 중복된 영역을 제거하여서 더해주면 된다.
unordered_set을 활용해 줬었는데 set으로 수정하니 더 빨라졌다.
unordered_set이 정렬을 안 한다는 점에서 시간이 더 빨라 보이지만 때에 따라 시간이 더 걸릴 수 있다.