농장 관리 - 1245

문제

풀이

import java.util.Scanner;

// 농장관리 - DFS - G5
public class ex1245 {

    static int n,m,answer=0;
    static int[][] board;
    static boolean[][] visit;
    static int[] dx = {0,1,1,1,0,-1,-1,-1};
    static int[] dy = {1,1,0,-1,-1,-1,0,1};
    static boolean flag = true;

    public static void DFS(int x,int y){
        for(int i=0; i<8; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && nx<n && ny>=0 && ny<m){
                if(board[x][y]<board[nx][ny]) flag = false;
                if(!visit[nx][ny] && board[x][y]==board[nx][ny]){
                    visit[nx][ny]=true;
                    DFS(nx,ny);
                }
            }
        }

    }
    public static void solution(){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(!visit[i][j]){
                    flag = true;
                    DFS(i,j);
                    if(flag) answer++;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        board = new int[n][m];
        visit = new boolean[n][m];

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                board[i][j] = sc.nextInt();
            }
        }

        solution();
        System.out.println(answer);
    }
}

농장의 봉우리 수를 찾는 문제이다. 주변에 대각선포함 8방향 기준으로 자신보다 높은 봉우리가 없어야 봉우리로 취급한다. 기본적인 DFS 템플릿을 가지며, flag를 이용해서 주변에 높은 봉우리가 없으면 true를 유지시켜 answer++해주고, 만약 주변에 높은 산이 있다면 상태를 flag로 바꿔준다. 그리고 자신과 높이가 같은 산이 있다면 방문체크를 해주면서 DFS()를 호출시켜준다. 그렇게 되면 solution()에서 다시 방문하지 않게된다. 그렇게 flag가 DFS에서 true로 남게 되면 봉우리!!!!!!!!