[백준 1245번] 농장 관리 - JAVA

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

1245번: 농장 관리

풀이

사용한 알고리즘: BFS

 

풀이전략

1. 주어진 입력을 2차원 배열에 작성한다.

2. (0,0)에서 (N-1,M-1)까지 각각의 인덱스를 BFS 탐색한다.

3. 특정 인덱스에서 주변에 인접한 모든 방향 탐색 중,

   작성한 2차열 배열 인덱스를 넘어서지않고, 방문하지 않았으며 그래프상 같은 수를 가진 경우

   방문처리하고 해당 인덱스를 Inqueue한다.

4. BFS 탐색 중 그래프상 인접한 값이, 현재 인덱스에서의 그래프상 큰 값이 하나라도 있으면 

   산봉우리 후보에서 탈락시킨다.

 

제출코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N,M;
    static int graph[][];
    static boolean visited[][];

    static int dx[]={-1,-1,0,1,1,1,0,-1};
    static int dy[]={0,1,1,1,0,-1,-1,-1};
    static boolean condition;

    static class Pos{
        int x;
        int y;
        public Pos(int x,int y){
            this.x=x;
            this.y=y;
        }
    }

    static void bfs(int x,int y){
        Queue<Pos> q = new LinkedList<>();
        q.offer(new Pos(x,y));
        visited[x][y]=true;
        while(!q.isEmpty()){
            Pos now = q.poll();
            for(int i=0;i<8;++i){
                int mx=now.x+dx[i];
                int my=now.y+dy[i];
                if(mx>=0 && mx<N && my>=0 && my<M){
                    if(graph[now.x][now.y]<graph[mx][my]){
                        condition=false;
                    }
                    if(!visited[mx][my] && graph[now.x][now.y]==graph[mx][my]){
                        visited[mx][my]=true;
                        q.offer(new Pos(mx,my));
                    }
                }
            }
        }

    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        graph=new int[N][M];
        visited=new boolean[N][M];

        for(int i=0;i<N;++i){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<M;++j){
                graph[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        int resultCount=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<M;++j){
                if(!visited[i][j]){
                    condition=true;
                    bfs(i,j);
                    if(condition) ++resultCount;
                }
            }
        }
        System.out.println(resultCount);
    }
}