백준 1245 농장 관리(JAVA)

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

1245번: 농장 관리

 

 

 

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_BJ_1245_농장관리 {
    static int n, m, ans;
    static int[][] map;
    static boolean[][] visited, topMap;
    // 상 하 좌 우 왼위 오위 왼아 오아
    static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        topMap = new boolean[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++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(map[i][j]!=0 && !topMap[i][j])
                    bfs(i, j);
            }
        }
        System.out.println(ans);

    }//main
    private static void bfs(int x, int y){
        Queue<int[]> q = new ArrayDeque<>();
        ArrayList<int []> top = new ArrayList<>();

        visited = new boolean[n][m];
        visited[x][y] = true;
        q.offer(new int[] {x, y});

        while(!q.isEmpty()){
            int[] cur = q.poll();

            for(int i=0; i<8; i++){
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if(check(nx, ny) && !visited[nx][ny]){
                    if(map[nx][ny] > map[cur[0]][cur[1]]) //현재보다 더 높은 지점 있으면 return
                        return;
                    else if(map[nx][ny] == map[cur[0]][cur[1]]){
                        q.offer(new int[] {nx, ny});
                        top.add(new int[] {nx, ny});
                    }
                    visited[nx][ny] = true;
                }//if
            }
        }//while
        for(int i=0; i<top.size(); i++){
            int[] cur = top.get(i);
            topMap[cur[0]][cur[1]] = true;
        }
        ans++;
    }//bfs

    private static boolean check(int x, int y){
        if(x<0 || y<0 || x>=n || y>=m)
            return false;
        return true;
    }
}

생각할 거리!!

 

1. 전체 맵을 탐색하면서 bfs를 돌린다.

   1-1. 이때, map이 0이 아니거나, 산봉우리라고 판단하지 않은 위치만 돌린다!

2. bfs에서 현재 기준을 잡고 있는 위치보다 인접한 곳에 높은 곳이 존재하는지 확인한다.

    2-1. 더 높은 곳이 있다면 바로 return하여 빠져나온다

    2-2. 현재 위치와 같은 곳이 있다면, 산봉우리 List(top)에 저장해두고, 큐에도 삽입한다.

    2-3. 방문 처리를 한다.

3. bfs가 끝난 후 산봉우리를 체크해준다.(이 상태까지 왔다면 bfs로 탐색한 위치가 산봉우리가 맞다는 의미와 같다)

4. 산봉우리 개수를 하나 올려준다.

 

 

쉬운듯 했지만,,, 잘 못풀었다...

다시 풀어보자!!

 

 

 

참고한 블로그

https://velog.io/@somyeong0623/%EB%B0%B1%EC%A4%80java-1245.-%EB%86%8D%EC%9E%A5-%EA%B4%80%EB%A6%AC

[백준/java] 1245. 농장 관리