[백준] 18111번 마인크래프트 JAVA (자바) 풀이

문제 18111

 

• 마인크래프트는 1 × 1 × 1 크기의 블록들로 건축 가능
  
  
• 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업 필수
  
  
• 세로 N, 가로 M 크기의 집터
  
• 내가 가진 블럭 B
• 집터 맨 왼쪽 위의 좌표는 (0, 0)
  
  

1. 블록을 제거해 인벤토리에 넣기 = 2초 소요
2. 인벤토리에서 블록 하나를 꺼내어 놓기 = 1초 소요
   

• 땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력해라
  (집터 아래에 빈 공간은 존재 X, 집터 바깥에서 블록 수집 X, 땅의 높이는 256블록을 초과 X, 음수 X) 

 

 

[입력]

 

 :  첫째 줄에 N, M, B (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

 :  둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이

    

 :  (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이 ( 땅의 높이는 256보다 작거나 같은 자연수 또는 0)

3 4 99
0 0 0 0
0 0 0 0
0 0 0 1

 

 

 [출력]

 :  첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이 출력
    (답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력)

2 0

 

 

 [문제접근]

 

• 
  
  → 
  
  
• 
  
  → 
  
  
• 
  
  → 
  
• bfs를 true / false 로 구분하기 위해 boolean 타입 사용
  

 

[참고]

 

 

 

 [코드]

import java.util.*;
import java.io.*;
public class Main{
    static int arr[][];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    static int timelimit = Integer.MAX_VALUE;
    static int N,M,B;
    static int result =0;
    public static void main(String[]args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
                min = Math.min(min, arr[i][j]);
                max = Math.max(max, arr[i][j]);
            }
        }
        for(int k=max; k>=min; k--){
            int time = 0;
            int block = B;
            for(int i = 0; i<N;i++){
                for(int j=0; j<M;j++){
                    if(arr[i][j]>k){
                        block+=(arr[i][j]-k);
                        time+=(arr[i][j]-k)*2;
                    }
                    else if(arr[i][j]<k){
                        block-=(k-arr[i][j]);
                        time+=(k-arr[i][j]);
                    }
                }
            }
        
        if(block>=0 && time < timelimit){
            result = k;
            timelimit = time;
        }
        }
        System.out.println(timelimit+" "+result);
        
    }
    
}

 

 [해설]
     

 :  static int arr[][];  배열판 생성
    static int max = Integer.MIN_VALUE;  max값
    static int min = Integer.MAX_VALUE;  min값
    static int timelimit = Integer.MAX_VALUE;  time도 받을 입력 중 가장 큰 것으로
    static int N,M,B;
    static int result =0;  결과 초기화
        
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());  가로
        M = Integer.parseInt(st.nextToken());  세로
        B = Integer.parseInt(st.nextToken());  블럭수
        arr = new int[N][M];  배열판 초기화
        
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());  배열판에 가진 높이 입력받기
                min = Math.min(min, arr[i][j]);  높이 최소값 출력
                max = Math.max(max, arr[i][j]);  높이 최대값 출력
            }
        }
        for(int k=max; k>=min; k--){  높이 맨 위에서부터 시작해서 아래까지 내려가기
            int time = 0;  소요시간
            int block = B;  가진 블럭수
            for(int i = 0; i<N;i++){
                for(int j=0; j<M;j++){
                    if(arr[i][j]>k){  제한블럭보다 현재블럭이 높다면
                        block+=(arr[i][j]-k);  블럭을 인벤토리에 넣어야해서 블럭 +
                        time+=(arr[i][j]-k)*2;  소요시간은 2초 씩 추가
                    }
                    else if(arr[i][j]<k){  제한블럭보다 현재블럭이 더 낮다면
                        block-=(k-arr[i][j]);  블럭 인벤토리에서 빼와야 하기 때문에 블럭 -
                        time+=(k-arr[i][j]);  소요시간은 1초 씩 추가
                    }
                }
            }
        
        if(block>=0 && time < timelimit){
            result = k;  최종 제한 블럭 출력
            timelimit = time;  최종 시간 출력
        }
        }
        System.out.println(timelimit+" "+result); 결과 출력
        
    }
    
}

 

 

이제 풀어보러 갈께요 :)

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *

 

 

18111번: 마인크래프트