문제 링크
15573번: 채굴
첫째 줄에 N, M, K가 주어진다. (1 ≤ N, M ≤ 1000, 1 ≤ K ≤ N × M) 둘째 줄부터 맨 위의 광물들부터 순서대로 N줄 동안 M개의 광물의 강도 Si, j가 주어진다.(i = 1, 2, ...,
www.acmicpc.net
주의사항
- JAVA를 사용하여 프로그램을 사용하였습니다.
- 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.
public class Main{
public static void main(String[] args){
}
}문제 설명
접근 방법
이 문제에 핵심
1. N × M 크기의 광물들이 존재하며, 각 광물에는 강도가 존재합니다.
2. 채굴기의 성능 이하의 광물만 채굴이 가능합니다.
3. 광물을 채굴할 때에는 공기과 맞닿아 있어야 하며, 최하단은 바닥으로 막혀있습니다.
4. K개 이상 채굴할 수 있는 채굴기의 최소 성능을 결과로 출력합니다.
알고리즘 진행 순서.
1. 입력된 정보를 저장합니다.
2. 이분탐색과 BFS을 통해서 채굴기의 성능을 탐색합니다.
3. 탐색한 채굴기의 성능의 최소값을 결과로 출력합니다.
이분 탐색(채굴기 성능 탐색하기)
이분 탐색을 통해서 채굴기의 성능을 탐색합니다.
Start : 광석의 강도의 최소 값
End : 광석 강도의 최대 값
이분 탐색을 진행할 때에는 2가지 경우로 나뉘게 됩니다.
1. 채굴기의 성능이 mid일 때 K개 이상 광물을 캘 수 있을 때
최소의 성능을 탐색하기 위해서 작은 범위에서 탐색합니다.
end = mid - 1
2. 채굴기의 성능이 mid일 때 K개 이상 광물을 캘 수 없을 때
현재 성능이 불가능하기 때문에 더 큰 범위에서 탐색합니다.
start = mid + 1
BFS(채굴 가능한 광석 개수 탐색)
공기와 항상 맞닿는 부분을 확인해서 채굴할 수 있으면 Queue<>담습니다.
이후 BFS 탐색을 진행하여 {상, 하, 좌, 우}의 공기가 있는지 확인함으로써 채굴 가능의 광석 개수를 탐색합니다.
※예제 입력 과정을 살펴보시면 이해하시기 편하실 것입니다.
예제입력 1.
1. 입력된 정보를 저장합니다.
N : 5
M : 5
K : 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 |
2. 이분탐색과 BFS을 통해서 채굴기의 성능을 탐색합니다.
광석이 항상 공기에 맞닿는 부분
이분 탐색 진행
start = 2(광석 중 강도 최소 값)
end = 3(광석 중 강도 최대 값)
mid = (2 + 3) ÷ 2 : 2
채굴기 성능이 2(mid)일 때
| 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 |
초기 공기에 맞닿는 부분에 채굴 가능한 광석이 없기 때문에 BFS을 진행해도 채굴할 수 있는 광석은 0개입니다.
채굴기의 성능이 2일 때 캐낸 광석 : 0개
K개 이상 광물을 캘 수 없기 때문에
start = mid + 1 : 3
다음 이분 탐색 진행
start = 3(광석 중 강도 최소 값)
end = 3(광석 중 강도 최대 값)
mid = (3 + 3) ÷ 2 : 3
채굴기 성능이 3(mid)일 때
| 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 |
초기 공기에 맞닿는 부분에 채굴 진행 후 BFS 탐색 진행(빨간 부분 채굴 가능)
| 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 |
초기 채굴한 광석을 기준으로 BFS탐색을 돌렸을 때 캐낸 광석(노란색 부분)
채굴기의 성능이 2일 때 캐낸 광석 :25개
K개 이상 광물을 캘 수 있기 때문에
end = mid - 1 : 2
start ≤ end의 조건에 벗어나므로 이분탐색 종료!
3. 탐색한 Count의 값을 결과로 출력합니다.
이분탐색으로 얻은 최소 성능의 값: 3(start)
3을 결과로 출력합니다.
- BufferedReader를 사용하여 입력되는 정보를 저장합니다.
- StringTokenizer를 이용하여 행렬의 크기 정보를 띄어쓰기 기준 저장합니다.
- search함수를 이용해서 K개 이상 채굴할 수 있는 최소 성능을 탐색합니다.
- 탐색을 통해 얻은 최소 성능을 BufferedWriter 저장합니다.
- BufferedWriter에 저장된 결과를 출력합니다.
- search함수는 이분탐색을 통해서 채굴기의 최소 성능을 탐색합니다.
- check함수는 채굴기 성능이 mid일 때 채굴할 수 있는 광석이 K개 이상인지 확인합니다.
- check함수는 캐낼 수 있는 광석의 개수를 구할 때 BFS을 이용해서 구합니다.
결과코드
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
//광물의 위치 관련 정보 클래스
static class Pair{
int x, y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
}
//광석 강도 저장 배열
static int[][] mineral;
static int N, M, K;
static int[] dr = {-1, 1, 0, 0}; //상하좌우 y 변경값
static int[] dc = {0, 0, -1, 1}; //상하좌우 x 변경값
public static void main(String[] args) throws IOException {
//입력값 처리하는 BufferedReader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//결과값 출력하는 BufferedWriter
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());
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
mineral = new int[N][M];
//광석 정보 저장 및 최대, 최소값 구하기
for(int i=N-1;i>=0;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 = search(min, max);
//최소 성능 BufferedWriter 저장
bw.write(String.valueOf(result));
bw.flush(); //결과 출력
bw.close();
br.close();
}
//이분 탐색을 통해 채굴기 최소 성능의 값을 구하는 함수
static int search(int min, int max){
//start : 강도 최소 값
//end : 강도 최대 값
int start = min;
int end = max;
//이분 탐색 진행
while(start <= end){
int mid = (start + end) / 2;
//강도가 mid일 때 캐낼 수 있는 광석이 K개 이상일 때
if(check(mid)){
end = mid - 1;
}else{ //강도가 mid일 때 캐낼 수 있는 광석이 K개 미만일 때
start = mid + 1;
}
}
return start; //최소 성능 정보 반환
}
//성능에 따른 광물 채굴 가능한 개수를 BFS으로 탐색하는 함수
static boolean check(int mid){
Queue<Pair> q = new LinkedList<>();
//광물 캐낸 여부 배열
boolean[][] visited = new boolean[N][M];
//초기 항상 공기에 맞닿는 부분 Queue 저장 및 캐낸 여부 변경
for(int i=0;i<N;i++){
if(mineral[i][0] <= mid){
q.offer(new Pair(i,0));
visited[i][0] = true;
}
if(mineral[i][M-1] <= mid){
q.offer(new Pair(i,M-1));
visited[i][M-1] = true;
}
}
for(int i=1;i<M-1;i++){
if(mineral[N-1][i] <= mid){
q.offer(new Pair(N-1,i));
visited[N-1][i] = true;
}
}
int cnt = q.size();
//BFS진행
while(!q.isEmpty()){
Pair cur = q.poll();
//상하좌우 공기가 있는 부분 찾기
for(int i=0;i<4;i++){
int tempR = cur.x + dr[i];
int tempC = cur.y + dc[i];
//광석이면서 공기를 맞닿을 때
if(inSpace(tempR,tempC) && !visited[tempR][tempC] && mineral[tempR][tempC] <= mid){
q.offer(new Pair(tempR,tempC));
visited[tempR][tempC] = true;
cnt++;
}
}
}
//채굴한 개수가 K개 이상일 때 : True, 미만일 때 : False
return cnt >= K;
}
//탐색하려는 공간이 광석이 존재하는 곳인지 확인하는 함수
static boolean inSpace(int r, int c){
if(r >= 0 && c >= 0 && r < N && c < M){
return true;
}
return false;
}
}'백준' 카테고리의 다른 글
| [백준, Java] 27210번, 신을 모시는 사당(누적합, DP) (4) | 2024.01.03 |
|---|---|
| [백준, Java] 17129번, 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유(BFS) (2) | 2023.12.27 |
| [백준, Java] 2866번, 문자열 잘라내기(이분 탐색) (2) | 2023.12.12 |
| [백준, Java] 1517번, 버블 소트(세그먼트 트리) (2) | 2023.12.11 |
| [백준, Java] 12991번, 홍준이의 행렬(이분탐색) (0) | 2023.12.09 |
댓글