[백준/Baekjoon] 1245 농장 관리 C++ :: Graph & BFS

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

1245번: 농장 관리

---

1. Logic

이 문제를 풀 때는 산봉우리의 의미를 잘 파악하는 것이 중요하다. 문제에서 정의한 산봉우리는 " 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. (여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이 모두 1 이하일 경우로 정의된다.)" 라고 했다

인접은 X, Y좌표가 1이하로 차이나야 하기 때문에 (1,1)을 중심으로 치면 (1,1)을 둘러 싼 좌표들이 모두 포함된다. 즉 일반적인 4방향 BFS가 아닌 8방향 BFS를 탐색하면 된다.

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)

 

 

 

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int graph[101][101];
bool vis[101][101];
//해당 높이가 가장 높은 산봉우리인지 확인
bool isPeak;

void BFS(int yy, int xx) {
    queue<pair<int, int>> q;
    
    q.push({yy, xx});
    vis[yy][xx] = true;
    
    while(!q.empty()) {
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        
        for(int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            //처음 BFS들어왔을 때 높이보다 높은게 있으면
            //이 높이는 산봉우리가 아니기때문에 카운트 X
            if(graph[yy][xx] < graph[ny][nx]) isPeak = false;
            if(vis[ny][nx]) continue;
            if(graph[yy][xx] != graph[ny][nx]) continue;
            q.push({ny, nx});
            vis[ny][nx] = true;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> graph[i][j];
        }
    }
    
    int cnt = 0;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(vis[i][j]) continue;
            if(!graph[i][j]) continue;
            isPeak = true;
            BFS(i, j);
            if(isPeak) cnt++;
        }
    }
    
    cout << cnt;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90