BOJ_15573_채굴 (Java)

[Gold III] 채굴 - 15573

문제 링크

성능 요약

메모리: 314360 KB, 시간: 1664 ms

분류

너비 우선 탐색, 이분 탐색, 그래프 이론, 그래프 탐색, 매개 변수 탐색

제출 일자

2025년 3월 16일 16:59:34

문제 설명

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

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

입력

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

출력

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

문제 풀이

간단한 bfs 문제다. 효율적으로 최소 D값을 찾기 위해 파라매트릭 서치를 사용했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M, K;
    static int [] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    static int[][] board;
    static boolean[][] visited;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_15573_채굴/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        board = new int[N][M];
        visited = new boolean[N][M];

        int maxD = 0;
        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());
                if(board[i][j] > maxD) maxD = board[i][j];
            }
        }

        int left = 1, right = maxD;
        int res = 0;
        while(left <= right) {
            int mid = left + (right - left) / 2;

            int count = countMines(mid);

            if(count >= K){
                res = mid;
                right = mid - 1;
            }
            else left = mid + 1;
        }

        System.out.println(res);
        br.close();
    }

    private int countMines(int mid) {
        visited = new boolean[N][M];
        int cnt = 0;

        for (int j = 0; j < M; j++) {
            if (!visited[0][j] && board[0][j] <= mid) {
                cnt += bfs(0, j, mid);
            }
        }

        for (int i=1; i<N; i++) {
            if(!visited[i][0] && board[i][0] <= mid) cnt += bfs(i, 0, mid);
        }

        for (int i=1; i<N; i++) {
            if(!visited[i][M-1] && board[i][M-1] <= mid) cnt += bfs(i, M-1, mid);
        }

        return cnt;
    }

    private static int bfs(int r, int c, int D){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;
        int cnt = 1;

        while(!queue.isEmpty()){
            int[] curr = queue.poll();

            for (int k=0; k < 4; k++){
                int nextR = curr[0] + dr[k];
                int nextC = curr[1] + dc[k];

                if(isValid(nextR, nextC) && !visited[nextR][nextC]){
                    if(board[nextR][nextC] <= D){
                        queue.offer(new int[]{nextR, nextC});
                        visited[nextR][nextC] = true;
                        cnt++;
                    }
                }
            }
        }

        return cnt;
    }

    private static boolean isValid(int nr, int nc) {
        return nr >= 0 && nr < N && nc >= 0 && nc < M;
    }
}