본문 바로가기

Hub Algorithm/이분 탐색

[BOJ] 백준 15573 : 채굴 (java)

728x90

🧪 15573 채굴


난이도 : 🌟 골드 3
유형 : 이분탐색

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

 

📝 문제

땅 위에 놓여있는 세로 N, 가로 M 길이의 광산에 1 × 1 광물 N × M개가 있으며, 각 광물은 고유의 강도Si, j를 가진다.

 

채굴기를 이용하여 이 광물들을 채굴하려고 한다. 채굴기는 공기와 맞닿아 있는 광물 하나를 골라 채굴할 수 있다. 바닥과 광물과만 맞닿아 있으면 채굴할 수 없다. 채굴기의 성능 D에 대해, 채굴기는 강도가 D 이하인 광물들만 채굴할 수 있다. 원하는 광물의 수 K 이상을 채굴할 수 있는 최소의 D를 구하여라.

 

 

입력

 

첫째 줄에 NMK가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ..., N, j = 1, 2, ..., M) (1 ≤ Si, j ≤ 106)

 

출력

 

K개 이상의 광물을 채굴할 수 있는 최소의 D를 구하여라.

 

🧐 핵심 로직 


1. 지도의 광물 강도를 기준으로 최소 조건을 만족하는 최대 강도를 구하기 위해 이분 탐색을 사용한다.

 

2. binarySearch 메서드는 강도의 범위를 설정한 뒤, 중간값을 기준으로 조건을 만족하는지 확인하며 탐색 범위를 조정한다.

    2 - a) 중간값이 조건을 만족하면 오른쪽 경계를 줄여 더 작은 값으로 탐색을 시도하고, 그렇지 않으면 왼쪽 경계를 늘려 강도를 증가시킨다.

 

3. checkMinerals 메서드는 BFS를 사용해 현재 기준 강도에서 조건을 만족하는지 확인한다.

    3 - a) 각 행과 열의 가장자리를 기준으로 시작점을 설정하고, BFS를 수행하며 강도가 기준 이하인 위치를 방문 처리한다.

    3 - b) BFS가 끝난 후 방문한 위치의 개수가 k 이상인지 확인해 조건 만족 여부를 반환한다.

 

4. BFS를 구현하기 위해 Node 클래스를 정의하여 현재 위치를 저장하며, 방문 처리를 위해 visited 배열을 사용한다.

 

5. 강도 값의 최소값과 최대값은 입력받은 배열에서 계산하며, 이를 이분 탐색의 초기 경계값으로 사용한다.

 

6. 최종적으로 조건을 만족하는 최소 강도를 출력한다.

 

💻 최종 코드 (1580 ms)


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

public class Main {

    static class Node{

        int x, y;

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

    static int n, m, k, minStrength, maxStrength;
    static int[][] minerals;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        minStrength = Integer.MAX_VALUE;
        maxStrength = Integer.MIN_VALUE;

        minerals = new int[n][m];
        for (int i = 0; i < n; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                minerals[i][j] = Integer.parseInt(st1.nextToken());
                maxStrength = Math.max(maxStrength, minerals[i][j]);
                minStrength = Math.min(minStrength, minerals[i][j]);
            }
        }

        int res = binarySearch();

        System.out.println(res);

        br.close();
    }

    private static int binarySearch() {

        int left = minStrength;
        int right = maxStrength;
        while (left <= right) {

            int mid = (left + right) / 2;

            if (checkMinerals(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    private static boolean checkMinerals(int target) {

        Queue<Node> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            if (minerals[i][0] <= target) {
                q.offer(new Node(i, 0));
                visited[i][0] = true;
            }
            if (minerals[i][m - 1] <= target) {
                q.offer(new Node(i, m - 1));
                visited[i][m - 1] = true;
            }
        }

        for (int i = 1; i < m - 1; i++) {
            if (minerals[0][i] <= target) {
                q.offer(new Node(0, i));
                visited[0][i] = true;
            }
        }

        int cnt = q.size();

        while (!q.isEmpty()) {

            Node curNode = q.poll();

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

                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if (visited[nx][ny]) continue;

                if (minerals[nx][ny] <= target) {
                    q.offer(new Node(nx, ny));
                    visited[nx][ny] = true;
                    cnt++;
                }
            }
        }

        return cnt >= k;
    }
}