문제 풀이

어떤 한 지점에서 8방향에 그 지점의 높이보다 높은곳이 없다면 산봉우리라고 간주하는데, 그 산봉우리의 개수가 주어진 입력에서 몇개인지 구하는 문제.

dfs와 산봉우리가 되는지 안되는지 찾아주는 flag를 이용해서 풀이한다.

먼저 내 코드에서는 flag가 false를 반환한다면 산봉우리라는 뜻이다.
dfs를 돌려서 일단 해당 지점에서 주변 8방향에 현재 높이보다 큰 곳이 있다면 flag=true 를 통해서 산봉우리가 아니라는 것을 명시해준다.

그리고 주변 8방향으로 dfs로 같은 높이이고 방문하지 않은곳으로 탐색해준다.
dfs를 통해서 산봉우리인지 아닌지 반환된 flag 값이 한번이라도 true를 반환했다면 그곳과 같은 높이로 이어진 산맥은 산봉우리가 아니다.

문제 링크

boj/1245

소스코드

PS/1245.java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {


	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int [][]arr= new int[101][101];
	static boolean [][]visit= new boolean[101][101];
	static int []dx = {1,0,0,-1,1,1,-1,-1};
	static int []dy ={0,1,-1,0,1,-1,1,-1};
	static int n,m;
	public static void main(String[] args) throws IOException {

		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		for(int i=0;i<n;i++){
			st = new StringTokenizer(br.readLine());

			for(int j=0;j<m;j++)
			{
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int ans =0 ;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++) {
				if(!visit[i][j] &&!dfs(j, i, arr[i][j]))
					ans++;
			}
		}
		bw.write(Integer.toString(ans));
		bw.flush();

	}
	static boolean dfs(int x,int y, int val)
	{
		boolean flag= false;
		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) {
				if(arr[ny][nx] > val)
					flag= true;
			}
			if(nx>=0 && ny>=0 && nx< m && ny <n && !visit[ny][nx] && arr[ny][nx] == val) {
				visit[ny][nx] = true;
				boolean ret = dfs(nx, ny, val);
				if(flag == false && ret ==true)
					flag=true;
			}
		}
		return flag;
	}

}