백준 1245: 농장 관리

문제 요약

농부 민식이가 관리하는 농장은 N×M 격자로 이루어져 있다. 민식이는 농장을 관리하기 위해 산봉우리마다 경비원를 배치하려 한다. 이를 위해 농장에 산봉우리가 총 몇 개 있는지를 세는 것이 문제다.


산봉우리의 정의는 다음과 같다. 산봉우리는 같은 높이를 가지는 하나의 격자 혹은 인접한 격자들의 집합으로 이루어져 있다. 여기서 "인접하다"의 정의는 X좌표 차이와 Y좌표 차이가 모두 1 이하인 경우이다. 또한 산봉우리와 인접한 격자는 모두 산봉우리의 높이보다 작아야한다.


문제는 격자 내에 산봉우리의 개수가 총 몇 개인지 구하는 것이다.

문제 분류

• 그래프 이론
• 그래프 탐색
• BFS
• DFS

문제 풀이

격자 그래프를 탐색하며 '산봉우리'를 탐색한다. 여기서, 자신 주변에서 자신과 같은 높이의 산을 일종의 컴포넌트로 묶어서 탐색할 수 있다. 즉, 컴포넌트 중 '산봉우리'인 컴포넌트의 개수를 세는 문제로 바꿀 수 있다.
내 주변에 자신보다 높은 산이 있다면 그 산이 포함된 컴포넌트는 산봉우리가 아닐 것이다. 그렇지 않다면 자신이 포함된 산의 컴포넌트는 '산봉우리'가 될 것이고 그 개수를 세면 된다.

풀이 코드

import java.util.*;
import java.io.*;
 
class Main
{
	static int n, m;
	static int ary[][];
	static int dir[][] = {{1, 0}, {1, 1}, {1, -1}, {0, 1}, {0, -1}, {-1, 1}, {-1, 0}, {-1, -1}};
    static boolean visited[][];
	public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        ary = new int[n][m];
        visited = new boolean[n][m];
        int cnt = 0;
        for(int i = 0; i < n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j = 0; j < m; j++)
        		ary[i][j] = Integer.parseInt(st.nextToken());
        }
        for(int i = 0; i < n; i++) {
        	for(int j = 0; j < m; j++) {
        		if(!visited[i][j]) {
        			visited[i][j] = true;
            		if(dfs(i, j)) cnt++;
        		}
        	}
        }
        System.out.println(cnt);
    }
    
    static boolean dfs(int i, int j) {
    	int ii, jj;
    	boolean ret = true;
    	for(int d = 0; d < 8; d++) {
    		ii = i + dir[d][0];
    		jj = j + dir[d][1];
    		if(ii >= 0 && ii < n && jj >= 0 && jj < m) {
    			if(ary[ii][jj] > ary[i][j])
        			ret = false;
    			if(!visited[ii][jj]) {
    				if(ary[ii][jj] == ary[i][j]) {
	    				visited[ii][jj] = true;
						ret = dfs(ii, jj) && ret;
        			}
    			}
    		}
    	}
    	return ret;
    }
}