글 읽기 - 연구소) C++ 시간초과

woogie 3년 전 0

어제 맞춘 문제를 다른방법으로 풀고 있는데 시간초과가 나옵니다.

어제는 main함수에서 벽 하나를 먼저 세우고 나머지 벽 두개는 함수를 만들어서 활용하였고

오늘은 벽세개 모두 함수를 만들어서 활용했습니다.

에러없이 잘돌아가는데 시간초과가 나옵니다.

ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);

=>>다음 코드를 사용하여 입출력 속도 문제도 해결한것 같은데 잘모르겠습니다.

혹시 고수님들 왜 이전 코드와는 달리 시간초과가 나오는지 알 수 있을까요?

또 해결할 수 있는 방법 주시면 감사하겠습니다. !_!

ps.이전 코드에서는 Map을 복사하여 활용하였고 이번에는 새로 Map을 복사하지 않았습니다.

#include<iostream>
#include<algorithm>
#include<queue>

#define MAX 8
using namespace std;

int N,M;
int Map[MAX][MAX];
int maxSize = 0;

int directX[] = {-1,1,0,0};
int directY[] = {0,0,-1,1};

void virusSpread() {

    int virusMap[MAX][MAX];
                
    for(int y=0; y<N; y++) {
        for(int x=0; x<M; x++) {
            virusMap[y][x] = Map[y][x];
        }
    }
    
    //큐 만들기
    queue<pair<int,int>> q;
    
    for(int y=0; y<N; y++) {
        for(int x=0; x<M; x++) {
            if(virusMap[y][x]==2) {
                q.push(make_pair(y,x));
            }
        }
    }
    
    while(!q.empty()) {
        //큐 꺼내기
        int x = q.front().second;
        int y = q.front().first;
        q.pop();
        
        //방향 check 
        for(int i=0; i<4; i++) {
            int nextX = directX[i] + x;
            int nextY = directY[i] + y;
           
            //배열의 유효성 check 
            if(nextX < 0 || nextY < 0 || nextX >= M || nextY >= N) {
                continue;
            }
            
            if(!virusMap[nextY][nextX]) {
                q.push(make_pair(nextY,nextX));
                virusMap[nextY][nextX] = 2;
            }
        }
    }

    int size = 0;
    
    for(int y=0; y<N; y++) {
      for(int x=0; x<M; x++) {
        if(virusMap[y][x]==0) {
          size++;
        }
      }
    }

    maxSize = max(maxSize,size);
    
    /*
    if(maxSize<empty) {
      maxSize = size;
    }
    */
}

void makeWall(int cnt) {
    if(cnt==3) {
        virusSpread();
        return;
    }
    
    for(int y=0; y<N; y++) {
        for(int x=0; x<M; x++) {
            if(!Map[y][x]) {
                Map[y][x] = 1;
                makeWall(cnt+1);
                Map[y][x] = 0;
            } 
        }
    }
}

int main(void) {
    
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> N >> M;
    
    for(int y=0; y<N; y++) {
        for(int x=0; x<M; x++) {
            cin >> Map[y][x];
        }
    }
    
    for(int y=0; y<N; y++) {
        for(int x=0; x<M; x++) {
            if(!Map[y][x]) {
                makeWall(0);
            } 
        }
    }
    
    cout << maxSize;
    
    return 0;
}

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

문제

문제

출처

ICPC

연구소) C++ 시간초과

woogie 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말