[백준] 1245 농장 관리 - Java

 

 

 

문제 출저

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

1245번: 농장 관리

 

 

 

문제 풀이

2차원 int 배열이 주어지고 산봉우리의 갯수를 구하는 문제입니다. 산봉우리란 같은 높이를 잇고 각각의 지점이 8방향 지점보다 크거나 같은 지점들입니다. 

 

 

BFS를 통해서 문제를 풀었습니다. 

등고선 개념을 생각했습니다. 8방향으로 탐색하면서 같은 크기의 지점들을 이었습니다. 그리고 이 지점들 하나하나 8방향을 탐색해서 높은 게 하나라도 있다면 false, 없다면 true로 나타냈습니다. true면 산봉우리이므로 answer +1 처리해 정답을 구했습니다. 

 

 

 

소스코드

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

/*
농장 관리
https://www.acmicpc.net/problem/1245

인접한 격자는 모두 높아야 한다.

같은 숫자를 전부 탐색한다
같은 숫자를 탐색하면 주변의 정보도 함깨 수집한다.
주변이 자신보다 큰 게 있다면 false 계속 없다면 true로 설정한다.
탐색 결과가 false면 산봉우리가 아니다
탐색 결과가 true면 산봉우리가 맞다.
 */
public class Main {

  static int n, m;
  static int[][] board;
  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 int answer;

  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());
    board = new int[n][m];

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

    visited = new boolean[n][m];

    for(int i = 0; i < n; i++) {
      for(int j = 0; j < m; j++) {
        if(board[i][j] > 0 && !visited[i][j]) {
          search(i, j);
        }
      }
    }

    System.out.println(answer);

  }

  public static void search(int y, int x) {

    visited[y][x] = true;
    Queue<Dot> que = new LinkedList<>();
    que.add(new Dot(y,x,board[y][x]));
    boolean flag = true;

    while (!que.isEmpty()) {
      Dot d = que.poll();

      for(int i = 0; i < 8; i++) {
        int ny = d.y + dy[i];
        int nx = d.x + dx[i];

        // 주변 탐색
        if(aroundCheck(ny,nx) && board[ny][nx] > d.height) {
          flag = false;
        }

        if(nextCheck(ny,nx,d.height)) {
          visited[ny][nx] = true;
          que.add(new Dot(ny, nx, d.height));
        }
      }
    }

    if(flag) answer++;
  }


  public static boolean aroundCheck(int y, int x) {
    if(y >= 0 && y < n && x >= 0 && x < m) {
      return true;
    }
    return false;
  }


  public static boolean nextCheck(int y, int x, int height) {
    if(y >= 0 && y < n && x >= 0 && x < m && !visited[y][x] && board[y][x] == height) {
      return true;
    }
    return false;
  }




  public static class Dot {
    int y;
    int x;
    int height;


    Dot(int y, int x, int height) {
      this.y = y;
      this.x = x;
      this.height = height;
    }

  }

}