[백준] 채굴 - Java

문제 링크

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

문제

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

 

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

입력

첫째 줄에 N, M, K가 주어진다. (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

5 5 10
3 3 3 3 3
3 2 2 2 3
3 2 2 2 3
3 2 2 2 3
3 2 2 2 3

예제 출력 1

3

풀이방법

• 이분 탐색과 BFS를 활용하여 풀이하였다.
  • 먼저 이분 탐색으로 채굴한 광석내에서 가장 작은 값(start)과 큰 값(end)을 설정해준다.
  • 이후, bfs를 수행하여 해당 위치에서 캘 수 있는 가장 큰 값을 count 해준다.
    • 이후에 마지막에 나온 cnt가 K보다 크다면 start를 mid + 1로, 아니라면 end를 mid - 1로 설정한다.
  • 해당 과정을 반복하여 start의 값을 리턴해주면 끝.

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class 채굴_15573 {
	static int N, M, K;
	static int[][] mineral;
	//상,하,좌,우
	static int[] dr = {-1, 1 ,0, 0};
	static int[] dc = {0, 0, -1, 1};
	static Deque<Mineral> dq;
	
	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());
		K = Integer.parseInt(st.nextToken());
		mineral = new int[N][M];
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				mineral[i][j] = Integer.parseInt(st.nextToken());
				min = Math.min(min, mineral[i][j]);
				max = Math.max(max, mineral[i][j]);
			}
		}
		
		int result = binarySearch(min, max);
		
		System.out.println(result);
	}
	
	public static int binarySearch(int min, int max) {
		int start = min;
		int end = max;
		
		while(start <= end) {
			//중간 값
			int mid = (start + end) / 2;
			
			if(checkMining(mid)) {
				end = mid - 1;
			}
			else {
				start = mid + 1;
			}
		}
		return start;
	}
	
	static boolean checkMining(int mid) {
		dq = new ArrayDeque<>();
		//방문 처리
		boolean[][] visited = new boolean[N][M];
		
		for(int i = 0; i < N; i++) {
			if(mineral[i][0] <= mid) {
				dq.offer(new Mineral(i, 0));
				visited[i][0] = true;
			}
			if(mineral[i][M-1] <= mid) {
				dq.offer(new Mineral(i, M - 1));
				visited[i][M - 1] = true;
			}
		}
		for(int i = 1; i < M - 1; i++) {
			if(mineral[0][i] <= mid) {
				dq.offer(new Mineral(0, i));
				visited[0][i] = true;
			}
		}
		
		//초기 광물은 주변을 다 캔 것으로 가정한다.
		int cnt = dq.size();
		
		//bfs
		while(!dq.isEmpty()) {
			Mineral m = dq.poll();
			
			for(int d = 0; d < 4; d++) {
				int nr = m.r + dr[d];
				int nc = m.c + dc[d];
				//캘수있는 광물이라면 추가
				if(nr >= 0 && nr < N && nc >= 0 && nc < M && !visited[nr][nc] && mineral[nr][nc] <= mid) {
					dq.offer(new Mineral(nr, nc));
					visited[nr][nc] = true;
					cnt++;
				}
			}
		}
		
		return cnt >= K;
	}
	
	public static class Mineral{
		int r;
		int c;
		
		public Mineral(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}

}

회고

• 좌표라 그런지 클래스를 만들어하는게 더 편한 것 같다.!