글 읽기 - 메모리 초과가 나는데.. 혹시 이걸 최적화할 수 있는 방법이 있을까요??

ldg1291 7년 전 0

불문제랑 거의 비슷한 방법으로 풀었는데, 여기선 메모리 초과가 나네요..

혹시 최적화 할 수 있는 방법이 있을까요??

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <string.h>

using namespace std;

vector<vector<char> > map;
vector<vector<int> > visited;

vector <pair <int, int> > water;

int n, m;

int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};

void bfs(pair <int, int> start) {
    
    visited[start.first][start.second] = 1;
    
    queue <pair <int, int> > que;
    
    que.push(start);
    
    int count = 0;
    
    while(!que.empty()) {
        
        int siz = water.size();
        for(int i=count; i<siz; i++) {
            for(int j=0; j<4; j++) {
                if(water[i].second + mx[j] >= 0 && water[i].second + mx[j] < m && water[i].first + my[j] >= 0 && water[i].first + my[j] < n) {
                    if(map[water[i].first + my[j]][water[i].second + mx[j]] == '.') {
                        map[water[i].first + my[j]][water[i].second + mx[j]] = '*';
                        water.push_back(make_pair(water[i].first + my[j],water[i].second + mx[j]));
                        count ++;
                    }
                    
                }
            }
        }
        
        pair <int, int> now = que.front();
        que.pop();
        
        for(int j=0; j<4; j++) {
            if(now.second + mx[j] >= 0 && now.second + mx[j] < m && now.first + my[j] >= 0 && now.first + my[j] < n) {
                if(map[now.first + my[j]][now.second + mx[j]] == '.' || map[now.first + my[j]][now.second + mx[j]] == 'D') {
                    if(map[now.first + my[j]][now.second + mx[j]] == 'D') {
                        printf("%d\n", visited[now.first][now.second]);
                        return;
                    } else {
                        visited[now.first + my[j]][now.second + mx[j]] = visited[now.first][now.second] + 1;
                        que.push(make_pair(now.first + my[j], now.second + mx[j]));
                    }
                }
            }
        }
        
    }
    printf("KAKTUS\n");
}

int main(int argc, const char * argv[]) {
    
    scanf("%d %d", &n, &m);
    
    pair <int, int> start;
    
    map.resize(n);
    visited.resize(n);
    
    for(int i=0; i<n; i++) {
        char tmp[1000];
        scanf("\n%s", tmp);
        for(int j=0; j<strlen(tmp); j++) {
            map[i].push_back(tmp[j]);
            visited[i].push_back(0);
            if(tmp[j] == 'S')
                start = make_pair(i, j);
            if(tmp[j] == '*')
                water.push_back(make_pair(i, j));
        }
    }
    
    bfs(start);
    
    return 0;
}

zlzmsrhak 7년 전 0

que에 push하기 전에 visited 배열을 확인해서, visited 되어 있는 경우 push를 하지 않는 방식으로 처리해야 하지 않을까요?

sgchoi5 7년 전 0

visited 를 따로 쓰지 않고, map 자체의 값을 업데이트 하는 것도 한 방법일 듯 합니다... . 을 방문한 경우(push) 할 때 : 로 변경하는..

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

문제

문제

출처

ICPC

메모리 초과가 나는데.. 혹시 이걸 최적화할 수 있는 방법이 있을까요??

ldg1291 7년 전 0

zlzmsrhak 7년 전 0

sgchoi5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말