2468 : 안전 영역 - 연결 컴포넌트, DFS, 최대 최소, 브루트포스, memset

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

2468번: 안전 영역

문제요약

connected component 개수의 최댓값 찾기

 

난이도

Silver 1

---

풀이 포인트

• DFS
  • 3차원으로 활용할 수 있음.
  • x,y좌표와 depth를 활용하여 탐색하는 식으로 활용
• 브루트포스(brute force)
  • brute: 무식한, force: 힘
  • 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과를 가져오는 완전탐색.
  • 높이를 하나씩 늘려가며 connected component가 최대가 되는 값을 탐색해야한다는 면에서 브루트 포스.
• 최대 최소 갱신 (max)
  • max(a,b) 
• memset을 이용한 초기화
  • memset(arrName, value, size)

bool arr[10];

memset(arr, false, sizeof(arr);

---

REVIEW

 

dfs, bfs 등의 그래프 탐색 방법이

1차원 노드간의 연결성을 논의할 때 뿐 아니라, 2차원 좌표를 탐색할 때도 사용할 수 있다는 것과

어떤 문제에 어떤 탐색법을 활용하면 좋을지 아주 약간 알아가고 있는 것 같다.

 

구현 코드를 이해는 하겠는데 자꾸 응용해 내가 구현을 하면 오답이 뜬다.

테스트케이스는 모두 통과했으나 또 오답.

 

여튼, DFS의 리프노트까지 거슬러가는 재귀적 특성을 활용해 연결 요소 개수를 구할 수 있다는 것은 확실히 파악했다.

 

나는 일정 이상 높이인 것을 따로 1,0 배열로 만들어준 후에, DFS로 2차원 좌표를 탐색하는 로직을 짰는데

모범 답안은 depth 즉 높이까지 3차원 좌표로 구성해, DFS의 매개변수를 3개로 받아 한 번에 처리를 하더라.

알아 두기.

 

---

CODE

#include <bits/stdc++.h>
using namespace std;

int a[101][101], visited[101][101], n, temp, ret = 1;
int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};

void dfs(int y, int x, int d){
    visited[y][x] = 1;

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

        if(ny < 0 || nx < 0 || ny >= n || nx >=n) continue;
        if(!visited[ny][nx] && a[ny][nx] >d) dfs(ny,nx,d);
    }
    return;
}

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

    cin >> n;

    for(int  i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }

    for(int d = 1; d < 101; d++){
        fill(&visited[0][0], &visited[0][0] + 101 * 101, 0);
        int cnt = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(a[i][j] >d && !visited[i][j]){
                    dfs(i,j,d);
                    cnt++;
                }
            }
        }
        ret = max(ret, cnt);
    }
    cout << ret << '\n';
}

//내 코드
//max,k,maxcnt를 0으로 설정해서 틀렸었다. 항상 반례 체크하기

#include <bits/stdc++.h>
using namespace std;

//dfs로 방향벡터 탐색
const int MAX = 101;
int n, a[MAX][MAX],b[MAX][MAX], minn = 2, maxx,k,maxCnt = 1;
bool visited[MAX][MAX];

int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

void dfs(int x, int y){
    visited[x][y] = true;

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

        if(nx >=0 && nx < n && ny >=0 && ny < n){
            if(b[nx][ny]&& !visited[nx][ny]){
                dfs(nx,ny);
            }
        }
    }
}

int main(){

    cin >> n;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> k;
            a[i][j] = k;

            if(k < minn){
                minn = k;
            }

            if(k > maxx){
                maxx = k;
            }
        }
    }

    for(int m = minn ; m < maxx; m++){

        memset(b,false, sizeof(b));
        memset(visited, false, sizeof(visited));

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n;j++){
                if(a[i][j]>m) b[i][j] = 1;
            }
        }

        int cnt = 0;

        for(int i = 0; i<n;i++){
            for(int j = 0; j <n; j++){
                if(b[i][j] && !visited[i][j]){
                    dfs(i,j);
                    cnt++;
                }
            }
        }

        if(cnt > maxCnt){
            maxCnt = cnt;
        }
    }

    cout << maxCnt;

}