글 읽기 - 메모리 초과

leehj8687 4년 전 0

안녕하세요,

위의 문제를 풀다가 메모리 초과 오류가 나서 질문드립니다.

이제 막 알고리즘 공부를 시작한 입장이라 정확히 어디서 오류가 난 지 파악하기가 힘드네요.

n의 값이 20이 최대라 이 선언에서는 오류가 나지 않았을테고, BFS 탐색에서 중복된 부분이 큐에 들어가서 오류가 나지 않았을까 짐작하고 있습니다.

그래서 85~96 을 추가했지만, 오히려 틀렸다는 결과를 얻었습니다. BFS탐색 중에 중복된 값들이 큐에 들어가는 것의 처리를 어떻게 해야할 지 잘 모르겠네요.

아래의 코드로 주어진 예제 테스트케이스들은 통과했지만, n이 20일때 임의로 작성한 테스트케이스는 통과하지 못하네요.

고수분들의 조언을 기다립니다!!

감사합니다.

20x20 테스트케이스

100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <tuple>
using namespace std;

int n;
int rt = 987654321;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int a[21][21];
int b[22][22];

void bfs(int x, int y, int d1, int d2){
    memset(b, 0, sizeof(b));
    queue<pair<int,int>> q;

    // 경계선 값 채우기
    /*  (x, y), (x+1, y-1), ..., (x+d1, y-d1)
        (x, y), (x+1, y+1), ..., (x+d2, y+d2)
        (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
        (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)
     * */
    if(y - d1 <= 0 || y - d1 + d2 <= 0 || x + d1 + d2 > n){
        return;
    }

    for(int i = x, j = y; i <= x + d1; i++, j-- ){
        b[i][j] = 5;
    }
    for(int i = x, j = y; i <= x + d2; i++, j++){
        b[i][j] = 5;
    }
    for(int i = x + d1, j = y - d1; i <= x + d1 + d2; i++, j++){
        b[i][j] = 5;
    }
    for(int i = x + d2, j = y + d2; i <= x + d1 + d2; i++, j--){
        b[i][j] = 5;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(b[i-1][j] == 5 && b[i][j-1] == 5
               && b[i][j+1] == 5 &&b[i+1][j] == 5){
                b[i][j] = 5;
            }
        }
    }

    // 0,0 부터 채우자.
    q.push(make_pair(1,1));

    while(!q.empty()){
        int cx, cy;
        tie(cx, cy) = q.front(); q.pop();

        /*  1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
                2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
                3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
                4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N
              * */
        if( 1 <= cx && cx < x + d1 && 1 <= cy && cy <= y){
            b[cx][cy] = 1;
        }
        else if( 1 <= cx && cx <= x + d2 && y < cy && cy <= n){
            b[cx][cy] = 2;
        }
        else if( x + d1  <= cx && cx <= n && 1 <= cy && cy < y - d1 + d2 ){
            b[cx][cy] = 3;
        }
        else if(x + d2  < cx && cx <=  n && y - d1 + d2  <= cy && cy <= n ){
            b[cx][cy] = 4;
        }

        for(int dir = 0; dir < 4; dir++){
            int nx = cx + dx[dir];
            int ny = cy + dy[dir];

            // 범위 벗어났을 때
            if(nx <= 0 || nx > n || ny <= 0 || ny > n) continue;
            // 이미 방문함.
            if(b[nx][ny] != 0) continue;

//            if( 1 <= nx && nx < x + d1 && 1 <= ny && ny <= y){
//                b[nx][ny] = 1;
//            }
//            else if( 1 <= nx && nx <= x + d2 && y < ny && ny <= n){
//                b[nx][ny] = 2;
//            }
//            else if( x + d1  <= nx && nx <= n && 1 <= ny && ny < y - d1 + d2 ){
//                b[nx][ny] = 3;
//            }
//            else if(x + d2  < nx && nx <=  n && y - d1 + d2  <= ny && ny <= n ){
//                b[nx][ny] = 4;
//            }
            q.push(make_pair(nx,ny));
        }
    }



    // 값 계산
    vector<int> result(5, 0);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(b[i][j] == 0) return;
            else{
                if(b[i][j] == 1) result[0] += a[i-1][j-1];
                if(b[i][j] == 2) result[1] += a[i-1][j-1];
                if(b[i][j] == 3) result[2] += a[i-1][j-1];
                if(b[i][j] == 4) result[3] += a[i-1][j-1];
                if(b[i][j] == 5) result[4] += a[i-1][j-1];
            }
        }
    }

    int min, max;
    min = *min_element(result.begin(), result.end());
    max = *max_element(result.begin(), result.end());

    if(rt > max-min){
        rt = max-min;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    // x, y, d1, d2 의 조건에 맞는 모든 경우의 수를 BFS 탐색 진행.
    for(int d1 = 1; d1 <= n; d1++){
        for(int d2 = 1; d2 <= n; d2++){
            for(int x = 1; x <= n; x++){
                for(int y = 1; y <= n; y++){
                    // 기준점 (x, y)와 경계의 길이 d1, d2를 정한다.
                    // (d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
                    if(1 <= x && x + d1 + d2 <= n && 1 + d1 <= y && y + d2 <= n){
                        bfs(x, y, d1, d2);
                    }
                }
            }
        }
    }

    cout << rt << '\n';

    return 0;
}

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

문제

문제

출처

ICPC

메모리 초과

leehj8687 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말