백준, BOJ, 1245번, 농장 관리 C++ [CPP] ★★★

 

 

처음에 조금 헷갈렸다.

어렵진 않지만 헷갈리기 쉽다.

 

 

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

 

---

 

#맞은 풀이

#include<bits/stdc++.h>

using namespace std;

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


int mount[101][101];
bool visited[101][101];

int N,M;
bool isPeak;
int cnt = 0;

//이름만 DFS지 그냥 재귀를 이용한 것
void DFS(int x, int y){
    for(int dir = 0; dir<8; dir++){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        //범위 체크
        if(nx < 0 || nx >=N || ny < 0 || ny >= M)continue;
        
        //나보다 큰 봉우리라면 탐색이 끝났을 때. false가 되어있으므로 봉우리 아님.
        if(mount[x][y] < mount[nx][ny])isPeak = false;
        
        
        //방문 체크
        if(visited[nx][ny])continue;
        
        //나랑 높이가 같은 봉우리면 걔도 조사
        if(mount[x][y] == mount[nx][ny]){
            visited[nx][ny] = true;
            DFS(nx,ny);
        }
    }
    
    return;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> mount[i][j];
        }
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            if(visited[i][j])continue; //봉우리 중복 조사 x
            isPeak = true;
            visited[i][j] = true;
            DFS(i,j);
            if(isPeak)cnt++;
        }
    }
    
    cout << cnt << '\n';
    
    return 0;
}

 

여기선 인접하다가 4방향이 아니라 8방향인 것을 생각하고

visited을 기록하는 이유는 봉우리를 판단하기 위해 방문한 곳들은 무조건 봉우리거나 봉우리가 아니거나 둘 중 하나이기 때문에 다시 조사할 필요가 없다.

또한 DFS라고 했지만 단순히 재귀에 불과하다. 그냥 주변에 높이가 같은 것이 있는지 찾는 것이다.