백준 1245번: 농장 관리

문제 설명

• https://www.acmicpc.net/problem/1245
• 산봉우리의 개수를 찾는 문제입니다.
  8방향으로 인접하면서 높이가 동일하면 같은 봉우리 입니다.

접근법

• if(0 <= nx && nx < N && 0 <= ny && ny < M && !v[nx][ny])를 하면 안됩니다
  방문체크를 하게되면 나와 인접한 칸이 나보다 높은지를 판단할 수 없기 때문입니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int N, M;
	static int[] dx = { 1,1,1,0,0,-1,-1,-1 };
	static int[] dy = {1,0,-1,1,-1,1,0,-1 };

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		int[][] board = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				board[i][j] = sc.nextInt();
			}
		}
		
		boolean[][] v = new boolean[N][M];
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(v[i][j]) continue;
				if(board[i][j] == 0) {
					v[i][j] = true;
					continue;
				}
				
				if(BFS(new int[] {i,j},v,board))cnt++;
			}
		}
		System.out.println(cnt);
	}
	public static boolean BFS(int[] start,boolean[][] v,int[][] board) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		v[start[0]][start[1]] = true;
		int num = board[start[0]][start[1]];
		boolean flag = true;
		while(!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 8; d++) {
				int nx = now[0]+dx[d];
				int ny = now[1]+dy[d];
				if(0 <= nx && nx < N && 0 <= ny && ny < M) {

					if(board[nx][ny] > num) {
						flag = false;
					}
					if(v[nx][ny]) continue;
					
					if(board[nx][ny] == num) {						
						v[nx][ny] = true;
						q.add(new int[] {nx,ny});
					}
				}
			}
		}
		return flag;
	}
	

}