BOJ 15573

26 Feb 2020 • ProblemSolving

채굴

문제출처

문제 해석

  • NxM 크기의 광산이 있을 때, 채굴기가 원하는 광물의 수 K이상을 채굴할 수 있는 최소의 D를 구하는 문제입니다.
  • 채굴기는 공기와 맞닿아 있는 광물 하나를 골라 채굴할 수 있습니다.
  • 채굴기의 성능 D에 대해, 강도가 D이하인 광물들만 채굴할 수 있습니다.

설계(5)

  • 정해놓은 D가 있을 때, 채굴기가 채굴할 수 있는 수를 탐색하기 위해서는 O(NM)의 시간복잡도가 필요합니다.
  • D를 정하는데 범위가 1<= D <= 10^6 이므로, 완전탐색을 하면 시간초과가 될 것입니다.
  • D를 정하는데 이분탐색을 이용하여 O(logD)로 최적화시킬 수 있으며, 최종적으로 O(NMlogD)로 시간안에 해결이 가능합니다.
  • bfs탐색을 이용하여 채굴할 수 있는 수를 카운트해서 이분탐색을 통해 최소값을 갱신시킵니다.

구현(30)

코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
#define MAXN 1000

int N,M,K;
int map[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

bool possible(int limits){
    memset(visited,false,sizeof(visited));
    queue<pair<int,int> > q;
    int sum = 0;
    for (int i = 0 ; i < N; i++){
        if (!i){
            for (int j = 0 ;j < M; j++){
                if (map[i][j] <= limits){
                    visited[i][j] = true;
                    q.push({i,j});
                    sum++;
                }
            }
        }
        else{
            if (!visited[i][0] && map[i][0] <= limits){
                visited[i][0] = true;
                q.push({i,0});
                sum++;
            }
            if (!visited[i][M-1] && map[i][M-1]<=limits){
                visited[i][M-1] = true;
                q.push({i,M-1});
                sum++;
            }
        }
    }
    while (!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int k = 0 ;k< 4; k++){
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx>=N || ny>=M) continue;
            if (visited[nx][ny] || map[nx][ny]>limits) continue;
            visited[nx][ny] = true;
            q.push({nx,ny});
            sum++;
        }
    }
    return (sum>=K);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    for (int i = 0;i <N; i++){
        for (int j = 0 ;j<M;j++){
            cin >> map[i][j];
        }
    }
    int low = 1;
    int high = 1e6;
    int ans = 1e6;
    while (low <= high){
        int mid = (low + high) / 2;
        if (possible(mid)){
            high = mid -1;
            ans = mid;
        }
        else{
            low = mid + 1;
        }
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
  • “채굴기가 공기가 맞닿아 있는 광물 하나를 골라 채굴할 수 있다”라는 지문에 대해 의문점이 생긴게, 처음에 이해할 때 하나를 골라서 해당 채굴기가 채굴할 수 있는 광물의 개수를 카운트하는 것으로 이해를 하였습니다.
  • 위와 같이 구현했을 시, WA가 나왔습니다.
  • 알고보니 “가능한 모든 지점에서 채굴을 시작했을 때, 채굴할 수 있는 개수”가 정확한 요점이었습니다.
  • 조건에 맞는 모든 지점을 큐에 추가한 후, bfs를 탐색하도록 하여 맞는 결과를 도출할 수 있었습니다.
제출결과
  • 684ms

마무리

  • 이분탐색 + bfs 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 지문에 혼동이 있어 디버깅에 시간이 걸렸습니다.
 BOJ

Related Posts