16932번 모양 만들기

https://www.acmicpc.net/problem/16932

 

오랜만에 풀어보았다.

 

저번 풀이 : https://hsdevelopment.tistory.com/336

 

저번에 푼 풀이 로직이랑 똑같다.

 

1. dfs를 통한 그루핑 및 그룹 번호 표기, 동일한 그룹 내 1의 개수

2. 이중for문을 통해 0인 경우에만 동서남북 방향으로 좌표에 따른 그룹번호를 활용하여 개수를 더함.

(단, map을 통해서 동일한 그룹일 경우 무시)

 

#include <bits/stdc++.h>

using namespace std;

int m[1010][1010];
int R, C;
int group[1000011];
int dy[4] = { 1,  0, -1, 0 };
int dx[4] = { 0, -1, 0,  1 };
bool used[1010][1010];
int gm[1010][1010];

int dfs(int r, int c, int gn) {

    int ret = 1;

    used[r][c] = true;

    gm[r][c] = gn;

    for (int i = 0; i < 4; i++) {
        int y = r + dy[i];
        int x = c + dx[i];

        if (y < 0 || y >= R || x < 0 || x >= C || used[y][x] || m[y][x] == 0) {
            continue;
        }

        ret += dfs(y, x, gn);
    }

    return ret;
}

int main()
{
    int ans = 0, gn = 1;

    scanf("%d %d", &R, &C);

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (m[i][j] == 1 && !used[i][j]) {
                int cnt = dfs(i, j, gn);
                group[gn] = cnt;
                ++gn;
            }
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {

            map<int, bool> mm;

            if (m[i][j] == 0) {

                int sum = 0;

                for (int k = 0; k < 4; k++) {
                    int y = i + dy[k];
                    int x = j + dx[k];

                    if (y < 0 || y >= R || x < 0 || x >= C || m[y][x] == 0) {
                        continue;
                    }

                    if (mm.count(gm[y][x]) == 0) {
                        sum += group[gm[y][x]];
                        mm.insert({ gm[y][x], 1 });
                    }
                }

                ans = max(ans, sum);
            }
        }
    }

    printf("%d\n", ans + 1);

    return 0;
}