[코드트리 챌린저] 2주차 DFS - DFS / 안전 지대

 

https://www.codetree.ai/missions/2/problems/comfort-zone/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

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

int n,m;
int arr[55][55]; // 마을 저장용  
int visited[55][55]; // 방문 확인
int village[55][55]; // 높이에 따른 영역
int dx[4] = { -1,0,1,0 }; // 시계방향 
int dy[4] = { 0,1,0,-1 };


// 배열 범위 내 인지 판단
bool InRange(int nx, int ny) {
    return (0 <= nx && nx < n && 0 <= ny && ny < m);
}

// 갈 수 있는지 판단
bool Cango(int nx, int ny) {
    if (!InRange(nx, ny)) return false;
    if (village[nx][ny] == 0) return false;
    if (visited[nx][ny]) return false;

    return true;
}

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

        // 갈 수 있는 경우 true, dfs
        if (Cango(nx, ny)) {
            visited[nx][ny] = true;
            DFS(nx, ny);
        }
    }

}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

    int maxHeight = INT_MIN; // k 범위 정하기 위한 최고 높이 파악
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            maxHeight = max(maxHeight, arr[i][j]);
        }
    }
    
    int k = -1; // 영역이 가장 많을 때 높이
    int maxCnt = INT_MIN; // 가장 많은 영역의 수


    // 각 높이를 설정
    for (int height = 1; height <= maxHeight; height++) {

        int cnt = 0; // 영역 수 
        // 방문 한 곳 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = false;
            }
        }
        
        // 물에 잠기는 곳은 0으로 설정함
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                village[i][j] = arr[i][j];
                if (arr[i][j] <= height)
                    village[i][j] = 0;
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (village[i][j] != 0 && !visited[i][j]) {
                    visited[i][j] = true;
                    cnt++;
                    DFS(i, j);
                }
            }
        }


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


    cout << k << " " << maxCnt;



}

n,m을 입력받고 2차원 배열 arr을 입력 받음과 동시에 물의 높이 설정을 위하여 최고 높이를 파악합니다.

for문을 통해 높이를 1 ~ 최대 높이까지 하나 씩 설정해 가면서 영역이 얼마나 생기는지 계산합니다.

cnt는 영역의 수를 의미합니다. for문을 반복할 때 마다 모두 새로 계산해야하므로 visited 배열을 초기화합니다.

2중 for문을 통해 물의 높이보다 작아 물에 잠기게 되는 곳은 0으로 설정하여 village 배열을 채웁니다.

이후 village 배열을 하나씩 살펴보며 물에 잠기지 않고 방문하지 않은 곳을 시작으로 DFS를 진행합니다.
이때 cnt를 1 상승시킵니다.

이후 cnt와 maxCnt를 비교하여 k와 maxCnt를 갱신하고 출력하도록 합니다.