πŸ“– [λ°±μ€€μ•Œκ³ λ¦¬μ¦˜ 풀이] Q.2468 μ•ˆμ „ μ˜μ—­ 문제 풀이

πŸ“– 문제

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

πŸ” 접근법

Q.2468 μ•ˆμ „ μ˜μ—­ 문제 ν’€μ΄μž…λ‹ˆλ‹€.

μž…λ ₯으둜 μ£Όμ–΄μ§€λŠ” n*n 만큼의 μ˜μ—­μ—

각각의 μ˜μ—­ 높이가 μ£Όμ–΄μ§‘λ‹ˆλ‹€.

λΉ„κ°€ 내릴 λ•Œ 비에 μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ μ˜μ—­μ˜ μ΅œλŒ€ 개수λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.

λΉ„μ˜ 양에 따라 μ•ˆμ „ μ˜μ—­μ˜ κ°œμˆ˜κ°€ λ‹€λ₯΄λ―€λ‘œ μ΅œλŒ€ λΉ„μ˜ μ–‘κΉŒμ§€μ˜

λͺ¨λ“  경우의 수λ₯Ό μ‚΄νŽ΄λ΄μ•Όν•©λ‹ˆλ‹€.

κ°•μš°λŸ‰μ€ 0λΆ€ν„° λͺ¨λ‘ μž κΈ°λŠ” μ˜μ—­μ˜ μ΅œλŒ€ λ†’μ΄κΉŒμ§€ κ°€λŠ₯ν•©λ‹ˆλ‹€.

각 κ°•μš°λŸ‰μ— λ”°λΌμ„œ

bfs 탐색을 톡해 κ°•μš°λŸ‰λ³΄λ‹€ 높은 μ˜μ—­μ˜ μΈμ ‘ν•œ 지역 (κ·Έλž˜ν”„) 갯수λ₯Ό κ΅¬ν•˜λ©΄ λ©λ‹ˆλ‹€.

λ˜ν•œ μ΅œλŒ€ 개수λ₯Ό ꡬ해야 ν•˜λ―€λ‘œ

각 κ°•μš°λŸ‰μ— λ”°λ₯Έ μž κΈ°μ§€ μ•ŠλŠ” μ•ˆμ „ μ˜μ—­μ˜ 개수λ₯Ό 비ꡐ해 μ΅œλŒ€κ°’μ„ κ΅¬ν•˜λ©΄ λ©λ‹ˆλ‹€.

πŸ’» μ½”λ“œ


package problem.bfsdfs;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main_2468 {
    static int n;
    static boolean[][] visited;
    static int[][] area;
    static int moveX[] = {0, 0, -1, 1};
    static int moveY[] = {-1, 1, 0, 0};
    static int max = 0;
    static int maxArea = 0;
    static int count =0;

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        for (int h = 0; h <= max; h++) {
            visited = new boolean[n][n];
            count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i < 0 || j < 0 || i >= n || j >= n)
                        continue;
                    if (area[i][j] <= h || visited[i][j] == true)
                        continue;
                    solve(i,j,h);
                }
            }
            maxArea = Math.max(maxArea,count);
        }
        System.out.println(maxArea);
        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        area = new int[n][n];

        for (int i = 0; i < n; i++) {
            String temp[] = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                int height = Integer.parseInt(temp[j]);
                area[i][j] = height;
                max = Math.max(max,height);
            }
        }
    }

    public static void solve(int a, int b, int h) {
        Queue<int[]> queue = new LinkedList();
        queue.offer(new int[]{a, b});
        visited[a][b] = true;

        while (!queue.isEmpty()) {
            int coordinate[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x = coordinate[0] + moveX[i];
                int y = coordinate[1] + moveY[i];

                if (x < 0 || y < 0 || x >= n || y >= n)
                    continue;
                if (area[x][y] <= h || visited[x][y] == true)
                    continue;

                queue.offer(new int[]{x, y});
                visited[x][y] = true;
            }
        }
        count++;
    }
}

Written on January 7, 2021