백준 15573 채굴 (c++)

문제 URL : https://www.acmicpc.net/problem/15573

 

 

문제 접근법 :

bfs + parametric search의 혼용문제입니다.

D를 1부터 bfs탐색하시면 시간초과라는것은 바로 알겁니다. 그럼 적당한값을 줘야한다는건데

바로 그생각만하면 이분탐색을 이용해야한다는것을 느낄것입니다.

 

bfs탐색은 외부에서부터 해야하는데 외부라면

사이즈 크기를 더크게 잡아야합니다. 그러나 바닥은제외이므로

그림으로 설명하자면

를 외부로 만들어서 0,0에서 bfs를 돌려서 코드를 줄일수있겠죠?

물론 정사이즈로 만들어서 바깥부분부터 탐색해서 bfs를돌려도 됩니다. 좀 번거롭기 하겠지만요

 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int board[1003][1003];
int check[1003][1003];
int dy[4]={-1,0,1,0};
int dx[4]={0,1,0,-1};
int n,m,k;
void input(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>board[i][j];
        }
    }
}
bool isrange(int y,int x){
    return 0<=y&&y<=n && 0<=x&&x<=m+1;
}
int bfs(int d,int num){
    check[0][0]=num;
    queue<pair<int,int>> q;
    q.push({0,0});
    int cnt=0;
    while(!q.empty()){
        int y,x;
        tie(y,x)=q.front();
        q.pop();
        cnt+=board[y][x]?1:0;
        if (cnt>=k)return 1;
        for(int i=0;i<4;i++){
            int ny=y+dy[i];
            int nx=x+dx[i];
            if(isrange(ny,nx)&& board[ny][nx]<=d &&check[ny][nx]!=num){
                check[ny][nx]=num;
                q.push({ny,nx});
            }
        }
    }
    return 0;
}
void solve(){
    int l=1,r=1e8;
    int res = 1e8;
    int num=1;
    while(l<=r){
        int mid = (l+r)>>1;
        if(bfs(mid,num++)){
            res = min(res,mid);
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    cout<<res<<"\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    input();
    solve();

 
}

 

 

사실 파이썬으로 먼저 풀었는데 알고리즘은 똑같은데 메모리 초과나서 c++로 바꾸더니 맞더군요

파이썬 메모리가 그렇게 많이 잡아먹는건가?? 고민이 더필요할것같아요

from collections import deque
n,m,k = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
board = [[0 for i in range(m+2)]for i in range(n+1)]
check = [[0 for i in range(m+2)]for i in range(n+1)]
dy=[-1,0,1,0]
dx=[0,1,0,-1]

for i in range(n):
    for j in range(m):
        board[i+1][j+1]=l[i][j]
def isrange(y,x):
    return 0<=y<=n and 0<=x<=m+1
def bfs(d,t):
    q = deque()
    q.append((0,0))
    check[0][0]=t
    cnt = 0
    while q:
        y,x = q.popleft()
        cnt+= 1 if board[y][x]>0 else 0
        for i in range(4):
            ny =y+dy[i]
            nx = x+dx[i]
            if isrange(ny,nx) and board[ny][nx]<=d and check[ny][nx]!=t:
                q.append((ny,nx))
                check[y][x]=t    
    return cnt
res = int(1e9)
l,r =1,int(1e9)
num=1
while l<=r:
    mid = int((l+r)/2)
    if bfs(mid,num)>=k:
        res = min(res,mid)
        r = mid-1
    else:
        l= mid+1
    num+=1
print(res)

이건데 이코드는 메모리 초과 코드입니다.

혹시 왜 메모리 초과인지 아시면 댓글달아주심 감사하겠습니다.

 

 

궁금한점 혹은 모르는점

어떤질문이든 댓글은 언제나 환영입니다.