2468 안전 영역

문제 링크

• 나의 풀이

모든 높이를 순회하며 최대 안전지대의 수를 계산했다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

constexpr int dr[4] = { -1, 1, 0, 0 };
constexpr int dc[4] = { 0, 0, -1, 1 };

int m[100][100], chk[100][100];
int N, M;

bool isVaild(const int& r, const int& c)
{
    if (r < 0 || r >= N || c < 0 || c >= N || chk[r][c])
        return false;
    return true;
}

int bfs(int lv)
{
    int ret = 0;
    queue<pair<int, int>> q;

    memset(chk, 0, sizeof(chk));

    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < N; c++)
        {
            if (!chk[r][c] && m[r][c] > lv)
            {
                ret++;
                q.push({ r, c });
                chk[r][c] = 1;

                while (!q.empty())
                {
                    int rr = q.front().first;
                    int cc = q.front().second;
                    q.pop();

                    for (int d = 0; d < 4; d++)
                    {
                        int nr = rr + dr[d];
                        int nc = cc + dc[d];

                        if (isVaild(nr, nc) && m[nr][nc] > lv)
                        {
                            q.push({ nr, nc });
                            chk[nr][nc] = 1;
                        }
                    }
                }
            }
        }
    }
    

    return ret;
}

int dfs()
{
    int ret = 0;
    for (int lv = 0; lv < M; lv++)
    {
        ret = max(bfs(lv), ret);
    }
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int r = 0; r < N; r++)
    {
        for (int c = 0; c < N; c++)
        {
            cin >> m[r][c];
            if (m[r][c] > M)
                M = m[r][c];
        }
    }

    cout << dfs() << "\n";
}

• 다른사람 풀이

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };
int n, par[MXN*MXN],r,c,ck[MXN][MXN];
int f(int x) { return x - par[x] ? par[x] = f(par[x]) : x; }
pair<int, int> p[MXN*MXN];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n*n; i++) scanf("%d", &p[i].first), p[i].second = par[i]=i;
    sort(p, p + n*n);
    for (int i = n*n - 1; i >= 0; i--) {
        c++;
        ck[p[i].second / n][p[i].second%n] = 1;
        for (int j = 0; j < 4; j++) {
            int tx = p[i].second / n + fx[j], ty = p[i].second%n + fy[j],t=tx*n+ty;
            if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty] && f(t) != f(p[i].second)) par[f(t)] = f(p[i].second),c--;
        }
        if (!i || p[i - 1].first != p[i].first) r = r>c ? r : c;
    }
    printf("%d", r);
    return 0;
}

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

constexpr int MXN = 100, fx[] = { 1,-1,0,0 }, fy[] = { 0,0,1,-1 };

int n, par[MXN * MXN], r, c, ck[MXN][MXN];
pair<int, int> p[MXN * MXN];

void printDt()
{
    int lim = n * n;

    for (int i = 0; i < lim;)
    {
        do
        {
            cout << par[i];
            cout << " ";
            i++;
        } while (i % n);

        cout << "\n";
    }

    for (int r = 0; r < n; r++)
    {
        for (int c = 0; c < n; c++)
            cout << ck[r][c];
        cout << "\n";
    }
}

// f(x) : par[x] == x -> return x 
// f(x) : par[x] != x -> return f(par[x]) 동시에 par[x] = f(par[x])로 바뀜
int f(int x)
{
    if (x == par[x])
    {
        return x;
    }
    else // x != par[x]
    {
        return par[x] = f(par[x]);
    }
    // return x - par[x] ? par[x] = f(par[x]) : x;
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n * n; i++)
    {
        scanf("%d", &p[i].first);
        p[i].second = par[i] = i;
    }

    sort(p, p + n * n);

    // 최고 높이 -> 낮은 높이 순환
    for (int i = n * n - 1; i >= 0; i--)
    {
        // 현재 높이의 섬의 갯수인가?
        c++;
        // 방문함을 기록
        ck[p[i].second / n][p[i].second % n] = 1;
        
        // 4가지 방향을 방문함
        for (int j = 0; j < 4; j++)
        {
            int tx = p[i].second / n + fx[j];
            int ty = p[i].second % n + fy[j];
            // 현 위치
            int t = tx * n + ty;
            
            // ck[tx][ty] == 1, 이미 방문했어야 함 (의미 : 현 위치 보다는 높거나 같은 위치이다)
            // f(t : 새위치) != f(p[i].second : 이전위치)
            if (tx >= 0 && ty >= 0 && tx < n && ty < n && ck[tx][ty] && f(t) != f(p[i].second))
            {
                // par[f(t)] : 새 위치의 par[f(t)]는 이전 위치의 f(p[i].second)로 바뀐다.(꼭대기 위치 값)
                par[f(t)] = f(p[i].second);
                // 새 위치는 이전에 방문한 곳 다시 말해 현 위치 보다 높은 곳
                // 병합 되므로 위치의 갯수를 줄인다.
                c--;
            }
        }

        if (!i || p[i - 1].first != p[i].first)
        {
            r = r > c ? r : c;
        }
    }
    
    // 결론 : 제일 높은 지대부터 물을 빼면서 섬의 갯수를 새는 방법

    printf("%d", r);

    return 0;
}