[BOJ/Java] 농장 관리 (1245)

농장 관리 (1245)

1. 문제 분석

문제 개요

• 농장의 높이 정보가 주어졌을 때, 각 높이를 기준으로 주변을 탐색하여 봉우리를 찾는 문제이다. 봉우리란, 해당 지역보다 주변 모든 높이가 낮아야 하며, 같은 높이인 경우 연속된 지역도 포함된다. 이 문제는 DFS(깊이 우선 탐색)를 이용하여 해결할 수 있다.

입력 형식

• 첫 줄에 농장의 크기를 나타내는 N(행)과 M(열)이 주어진다.
• 다음 N개의 줄에는 M개의 농장의 높이 정보가 주어진다.

출력 형식

• 봉우리의 개수를 출력한다.

2. 알고리즘 종류

• DFS (깊이 우선 탐색)
  DFS를 사용하여 각 높이의 지역을 탐색하고, 그 지역이 봉우리인지를 판단하여 봉우리의 개수를 센다.

3. 주요 부분 및 코드 작성 방법

1. 농장 및 방문 배열 초기화

• 입력된 농장 높이 정보를 저장하고, 방문 여부를 기록할 visited 배열을 초기화한다.

2. DFS를 이용한 봉우리 탐색 및 결과 출력

• DFS를 사용하여 각 지역을 탐색하며, 봉우리인지 여부를 판단하여 그 개수를 증가시킨다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리 및 농장 초기화

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken()); // 농장의 행 크기
    M = Integer.parseInt(st.nextToken()); // 농장의 열 크기
  
    farm = 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++) {
            farm[i][j] = Integer.parseInt(st.nextToken());
        }
    }

  • 농장의 높이 정보를 입력받아 저장한다.

• 봉우리 탐색 및 결과 출력

    int answer = 0; // 봉우리 개수를 저장할 변수
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j]) { // 아직 방문하지 않은 경우
                flag = true; // 봉우리 여부를 판단하는 플래그 초기화
                DFS(i, j); // DFS로 탐색 시작
                if (flag) answer++; // 봉우리인 경우 개수 증가
            }
        }
    }
    System.out.println(answer); // 봉우리 개수 출력

  • 방문하지 않은 지역을 DFS로 탐색하여 봉우리를 찾고, 그 개수를 출력한다.

(2) DFS 함수 (DFS)

• DFS 탐색 및 봉우리 판단

    private static void DFS(int r, int c) {
        for (int i = 0; i < 8; i++) { // 8방향으로 이동
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; // 범위를 벗어나면 건너뜀
  
            if (farm[r][c] < farm[nr][nc]) flag = false; // 현재 위치보다 높은 지역이 있으면 봉우리가 아님
  
            if (visited[nr][nc] || farm[r][c] != farm[nr][nc]) continue; // 이미 방문했거나 높이가 다르면 건너뜀
            visited[nr][nc] = true; // 방문 처리
            DFS(nr, nc); // 재귀적으로 DFS 호출
        }
    }

  • 현재 위치에서 8방향으로 이동하며, 주변에 더 높은 지역이 있으면 봉우리가 아니라고 판단한다. 같은 높이의 지역은 계속 연결되어 탐색한다.

5. 전체 코드

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

public class BOJ1245 {
    static int N, M; // 농장의 크기 (행, 열)
    static int[][] farm; // 농장 높이를 저장할 배열
    static boolean[][] visited; // 방문 여부를 기록할 배열
    static boolean flag = true; // 봉우리 여부를 판단하는 플래그
    static int[] dr = {-1, 1, 0, 0, -1, -1, 1, 1}; // 8방향 이동을 위한 행 변화량
    static int[] dc = {0, 0, -1, 1, -1, 1, -1, 1}; // 8방향 이동을 위한 열 변화량

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 농장의 행 크기
        M = Integer.parseInt(st.nextToken()); // 농장의 열 크기

        farm = 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++) {
                farm[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int answer = 0; // 봉우리 개수를 저장할 변수
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) { // 아직 방문하지 않은 경우
                    flag = true; // 봉우리 여부를 판단하는 플래그 초기화
                    DFS(i, j); // DFS로 탐색 시작
                    if (flag) answer++; // 봉우리인 경우 개수 증가
                }
            }
        }
        System.out.println(answer); // 봉우리 개수 출력
    }

    // DFS를 이용해 봉우리를 탐색하는 함수
    private static void DFS(int r, int c) {
        for (int i = 0; i < 8; i++) { // 8방향으로 이동
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue; // 범위를 벗어나면 건너뜀

            if (farm[r][c] < farm[nr][nc]) flag = false; // 현재 위치보다 높은 지역이 있으면 봉우리가 아님

            if (visited[nr][nc] || farm[r][c] != farm[nr][nc]) continue; // 이미 방문했거나 높이가 다르면 건너뜀
            visited[nr][nc] = true; // 방문 처리
            DFS(nr, nc); // 재귀적으로 DFS 호출
        }
    }
}