[코딩테스트 C++] 안전 영역

오늘의 문제

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

안전 영역

접근 방식

• 우선 지대의 높이가 영역 수 변화의 key이므로 set에 높이를 저장한다. 그래야 모든 수를 비교하지 않는다
• 그리고 저장해놓은 높이마다 한번씩 dfs 영역찾기 로직을 돌린다.
• 이 로직에서 가야하지 않을 부분은 이번 비의 높이보다 작거나 같은 영역이다.
• 모든 높이에 대해 진행하고, 그 중 가장 큰 수를 출력한다.

나의 풀이

#include <iostream>
#include <set>
#include <string.h>
using namespace std;
const int MAX = 100;
int map[MAX][MAX];
int visit[MAX][MAX] = {false, };
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n;
int h;
set<int> num;

// 안전영역
void dfs(int a, int b){
    visit[a][b] = true;
    for(int i=0;i<4;i++){
        int ma = a+ dy[i];
        int mb = b+ dx[i];
        if(ma >= n || ma <0 || mb >= n || mb <0)
            continue;
        if(visit[ma][mb] == false && map[ma][mb]>h)
            dfs(ma, mb);
    }
}
long long solution(){
    int answer = 1;
    set<int>::iterator height = num.begin();
    for(int i=0;i<num.size();i++){
        h = *height;
        int cnt = 0;
        for(int a = 0;a<n;a++){
            for(int b = 0;b<n;b++){
                if(map[a][b] > h && visit[a][b] == false){
                    dfs(a, b);
                    cnt++;
                }
            }
        }
        memset(visit, false, sizeof(visit));
        answer = max(answer, cnt);
        height++;
    }
    return answer;
}

다른 풀이

#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;
}

배울 점

• 이사람은 소팅하여 어느지점까지 계산을 하고 멈췄다.시간초과하면 아렇게 하려했는데, 시간초과가 안나버렸었다. (^-^)a