[백준] 2468 안전 영역

Posted on | In

문제 설명

삘 붙어서 문제를 계속 풀고 있다!!! 그런데 신기하게도 계속 연결 요소와 관련된 문제가 걸린다. 그런데 굉장히 알맞은 순서로 문제가 걸려서 신기하긴 하다 ㅋㅋ 이 문제는 이전의 연결 요소의 개수 문제나 유기농 배추 문제처럼 basic하게 연결 요소를 count하는 게 아니라 조금의 응용이 들어간다. 그래프의 값이 0, 1로 표현 되서 연결 된다 vs 안된다 두개로 표현 되는 게 아니라 0 이상의 값을 가지고, 높이라고 표현한다. 그래서 일정 높이 이상이 되어야 안 잠긴다고 표현하고, 이 안 잠긴 노드끼리만 해서 그래프 탐색을 진행하고 연결 요소의 개수를 세는 것이다.

문제 풀이

문제 설명도 안하고 냅다 어떻게 푸는지를 설명한 거 같아서 문제가 뭔지부터 설명해야겠다 ..ㅎㅎ 문제는 지역의 높이 행보?를 input으로 준다. 결국 지역의 높이가 x,y로 2차원 배열 형태로 주어진다는 말이다!! n은 가로 세로 길이를 뜻한다. (가로길이=세로길이) 이때, 물이 k만큼 차게 되면 k보다 작은 위치의 높이들은 잠기게 된다. k랑 동일한 높이를 가진 위치 좌표는 잠기지 않는다. 결국 잠기지 않은 위치 좌표들에 대해서 그래프 탐색을 진행하고, 이렇게 되면 몇 번의 탐색이 진행되는지를 세면 된다. 여기서 기존의 연결 요소 문제보다 응용된 부분이 물이 차는 높이 k에 따라서 잠기는 위치 좌표들도 달라지게 되는데(k가 작을수록 살아남은 위치 좌표들이 많아지겠다), k를 바꿔 가면서 가장 최대의 그래프 탐색 횟수가 필요한 경우를 출력하면 된다. 따라서 k에 대한 for문이 dfs 바깥에서 한번 더 돌게 된다. 문제만 읽고 처음에 나는 k의 범위가 어디까지인지 파악할 수가 없어서 이 부분만 풀이를 아주 살짝 봤는데, nxn 지역에서 최대, 최소 높이를 k의 범위로 잡으면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <string.h>
using namespace std;

int n;
int adj[101][101];
int v[101][101];

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

void dfs(int sub, int y, int x){
    if(adj[y][x]-sub<0) return; // 잠기면 세지 마!
    v[y][x]=1;
    //printf("%d %d passed\n", y, x);

    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 && !v[ny][nx] && adj[y][x]-sub>=0) dfs(sub, ny, nx);
    }   
}

int cnt(int sub){
    int cnt=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            //printf("~%d %d\n", adj[j][i], sub);
            if(!v[j][i] && adj[j][i]-sub>=0){
                //printf("%d %d\n", j, i);
                cnt++;
                dfs(sub, j, i);
            }
        }
    }
    return cnt;
}
int main(){
    scanf("%d", &n);
    int min=101, max=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d", &adj[i][j]);
            if(adj[i][j]<min) min = adj[i][j];
            if(adj[i][j]>max) max = adj[i][j];
        }
    }

    //printf("%d %d\n", min, max);

    int max_k=0;
    for(int i=min;i<=max;i++){
        int k = cnt(i);
        //printf("k = %d\n", k);
        if(max_k<k) max_k=k;
        memset(v, 0, sizeof(v));
    }
    printf("%d\n", max_k);
    return 0;


}

코드 풀이

예전까지 문제 풀 때는 dfs 하나만 함수로 뺐었는데, 이 문제에서는 연결 요소의 개수를 세는 부분도 함수로 빼버렸다. 삼중 포문이 돈다고 생각하니까 헷갈려서 이렇게 했다. main안을 먼저 보면, scanf로 입력을 받으면서 min과 max를 계속 갱신해준다. 이 과정으로 홍수가 날 때의 물 높이의 범위를 구할 수 있다. 그 다음에는 이 min, max를 높이의 기준선으로 잡고 연결 요소를 하나의 k에 대해 각각 구해주면 된다. (위 코드의 k, max_k는 사실 물의 높이가 아니라 각 경우의 연결 요소의 개수를 의미한다. 헷갈리지 말기!!!) 이때 나는 cnt 함수를 정의해서 각 좌표에 있는 지역의 높이가 물의 높이보다 크거나 같은 경우에 dfs탐색을 진행 하도록 하였다. 이때 기존의 cnt할 때와 동일하게 이미 방문한 곳은 dfs와 cnt++을 해주지 않는다. 그리고 결국 dfs 함수로 들어가서, 잠기는 경우(물의 높이<지역의 높이)에는 바로 return 해주었다. 이후는 평소의 dfs와 동일하지만, sub 인자를 주어서 물의 높이>=지역의 높이 일 경우만 노드가 존재한다고 보았다. (dfs를 진행했다)