글 읽기 - 메모리 초과가 발생하는데 이유를 알수 있을까요??

revolution_2 6년 전 0

문제 접근은 일단 섬들마다 번호를 전체 부여하고 섬들 마다 가장 자리를 넓혀가면서 다른 섬에 도착하면 거리를 저장하는 형식으로 했는데

66퍼센트 정도가서 메모리가 초과해버리네요..

큐를 잘못 사용한것 같은데 이유를 알수 있을지 궁금합니다.

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int N;
int ans = 987654321;
int dr[4] = {0, 0, 1, -1};
int dc[4] = {1, -1, 0, 0};
vector<vector<int>> map;
vector<vector<int>> visited;
queue<pair<int, int>> q;

int copy() {
    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            map[i][j] = visited[i][j];
        }
    }

    return 0;
}

int queueClear() {
    while(!q.empty()) {
        q.pop();
    }
    return 0;
};

int main() {

    cin >> N;

    map.assign(100, vector<int>(100, 0));
    visited.assign(100, vector<int>(100, 0));

    for(int i = 0; i < N; i ++) {
        for(int j = 0; j < N; j ++) {
            cin >> map[i][j];
        }
    }

    // 구역 나누기
    int cnt = 1;
    for(int i = 0; i < N; i ++) {
        for (int j = 0; j < N; j++) {
            if(map[i][j] == 1 && !visited[i][j]) {
                q.push(make_pair(i, j));
                visited[i][j] = cnt;
                while(!q.empty()) {
                    int r = q.front().first;
                    int c = q.front().second;
                    visited[r][c] = cnt;
                    q.pop();

                    for(int i = 0; i < 4; i ++){
                        int nextR = r + dr[i];
                        int nextC = c + dc[i];

                        if(nextC >= 0 && nextR >= 0 && nextC < N && nextR < N) {
                            if(map[nextR][nextC] && !visited[nextR][nextC]) {
                                q.push(make_pair(nextR, nextC));
                            }
                        }
                    }
                }
                cnt ++;
            }
        }
    }

    cnt --;
    int check = 1;
    int finish;
    while(cnt --) {
        copy();
        queueClear();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == check) {
                    q.push(make_pair(i, j));
                }
            }
        }

        int temp_ans = 0;
        finish = 0;
        while(!q.empty()) {
            if(finish) {
                break;
            }

            long long loop = q.size();
            temp_ans ++;
            while(loop --){
                if(finish) {
                    break;
                }

                int r = q.front().first;
                int c = q.front().second;
                q.pop();

                for(int i = 0; i < 4; i ++){
                    int nextR = r + dr[i];
                    int nextC = c + dc[i];

                    if(nextC >= 0 && nextR >= 0 && nextC < N && nextR < N) {
                        if(!map[nextR][nextC]) {
                            map[nextR][nextC] = check;
                            q.push(make_pair(nextR, nextC));
                        } else if(map[nextR][nextC] != check) {
                            ans = (ans > temp_ans)? temp_ans : ans;
                            finish = 1;
                            break;
                        }
                    }
                }
            }
        }
        check ++;
    }

    cout << ans - 1;
    return 0;
}

djm03178 6년 전 1

제가 질문 게시판에 가장 많이 쓴 답변 중 하나가 이것입니다.

"BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다."

65줄이 여기에 해당됩니다.

revolution_2 6년 전 0

감사합니다 해결 했습니다.!!

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

문제

문제

출처

ICPC

메모리 초과가 발생하는데 이유를 알수 있을까요??

revolution_2 6년 전 0

djm03178 6년 전 1

revolution_2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말