글 읽기 - I need 도움, anyone help me!!!!!!!!!!!!

df1097 3년 전 0

풀이방법

1. virus[10]에 어떤 바이러스를 활성화시킬지 저장합니다.(이 부분은 dfs)를 이용
2. M개만큼 선택되었으면 spread함수를 통해 바이러스를 퍼뜨립니다.(이 부분은 queue를 이용한 bfs)

어디서 시간초과가 걸리는 것일까요............... 제발 저를 도와주세요. 탈모가 도질 것 같아요. 내 머리를 살려줘~!~!

#include <iostream>
#include <queue>
#include <cstring>

#define Max 1000000
#define Min(X, Y) ((X) < (Y) ? (X) : (Y))
#define limit 50

using namespace std;

int dy[4] = {-1,1,0,0};
int dx[4] = {0,0,-1,1};
int tempboard[limit][limit];
int board[limit][limit];
vector<pair<int, int>> possible;

bool virus[10];

int spread(int n, int rest){
    memset(tempboard, -1, sizeof(tempboard));
    queue<pair<int, int>> q;
    int ret = 0;
    int rrest = 0;
    for(int i=0; i<10; i++){
        if(virus[i]){
            q.push({possible[i].first, possible[i].second});
            tempboard[possible[i].first][possible[i].second] = 0;
        }
    }

    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        int tc = tempboard[ty][tx];
        q.pop();
        if(rest == rrest) break;

        for(int i=0; i<4; i++){
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if(ny >=n || nx >= n || ny < 0 || nx < 0 || tempboard[ny][nx] != -1 || board[ny][nx] == 1) continue;
            if(board[ny][nx] != 2) rrest += 1;
            tempboard[ny][nx] = tc + 1;
            if(tc+1 > ret) ret = tc+1;
            q.push({ny, nx});
        }
    }
    
    if(rrest < rest){
        ret = Max;
    }

    return ret;
}

int dfs(int n, int M, int depth, int rest, vector<pair<int,int>> possible, int index){
    int ret = Max;   

    if(depth == M) 
        return spread(n, rest);

    for(int i=index; i < possible.size() - M + depth + 1; i++){
        virus[i] = true;
        ret = Min(ret, dfs(n, M, depth + 1, rest, possible, i+1));
        virus[i] = false;
    }
    return ret;
}

int main(void){
    std::ios::sync_with_stdio(false);
    int N, M;
    cin>>N>>M;
    int rest = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>board[i][j];
            if(board[i][j] == 0) {
                rest += 1;
            }
            if(board[i][j] == 2) possible.push_back({i, j});
        }
    }
    for(int i=0; i<10;i++) virus[i] =false;
    int answer = dfs(N, M, 0, rest, possible, 0);
    if(answer == Max) answer = -1;
    cout<<answer<<endl;

    return 0;
}

df1097 3년 전 0

문제는

ret = Min(ret, dfs(n, M, depth + 1, rest, possible, i+1));

이부분이었다는 것을 꺠달았습니다. 변수 하나를 사용해서 미리 할당을 해두고 값을 비교하지 않고 저렇게 사용하니, 값을 비교할때 한번 시행되고, 값을 할당할때 한번 시행되고 이러면서 중복적으로 시행된다는 사실을 깨달았습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

I need 도움, anyone help me!!!!!!!!!!!!

df1097 3년 전 0

df1097 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말