글 읽기 - 메모리 초과인데 이유를 모르겠습니다

insightn777 4년 전 0

메모리 초과가 어떤 상황에서 발생하는지조차 모르겠습니다. ㅜㅜ

#include <iostream>
#include <algorithm>
#include <string>
#include <utility>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

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

    int test;
    cin >> test;
    
    int diri[] = {-1,0,1,0};
    int dirj[] = {0,-1,0,1};

    for ( int t = 0 ; t < test ; t++ ) {
            
        char board[1000][1000] = {' '};
        int visit[1000][1000] = {0};

        int w,h;
        cin >> w >> h;

        queue<pair<int,int>> fire;
        queue<pair<int,int>> man;
    
        int count = 0;
        char input;
        for (int i = 0 ; i < h ; i++) {         // 입력 받음
            for (int j = 0 ; j < w ; j++) {
                cin >> input;
                if (input == '@') {
                    man.push({i,j});
                    visit[i][j] == 1;
                } else if( input == '*' ) {
                    fire.push({i,j});
                    count++;
                }
                board[i][j] = input;
            }
        }       // 입력 끝


        int step = 0;
        bool loop = true;
        while(loop) {  // step 순회

            // 불이 번질 예정인 곳도 상근이는 못가니 불이 먼저 번졌다고 가정해버림

            int discount = count;
            count = 0;
            while
            (discount > 0) { // 이전에 큐에 넣은만큼 불번짐
                
                for (int d = 0 ; d < 4 ; d++) {
                    int ni = fire.front().first + diri[d];
                    int nj = fire.front().second + dirj[d];
                    if (ni < 0 || nj < 0 || ni >= h || nj >= w ) continue;      // 범위 넘어가면 패스
                    if (board[ni][nj] == '*' || board[ni][nj] == '#') continue; // 이미 불이거나 막히면 패스
                    board[ni][nj] = '*';
                    fire.push({ni,nj});
                    count++;
                }
                fire.pop();
                discount--;
            }

            while (loop) {
                if (visit[man.front().first][man.front().second] > step) {   // man step 이 초과하면 다음 스텝 순회로 넘김
                    step++;
                    break;
                }

                for (int d = 0 ; d < 4 ; d++) {
                    int ni = man.front().first + diri[d];
                    int nj = man.front().second + dirj[d];
                    if (ni < 0 || nj < 0 || ni >= h || nj >= w ) {  // 탈출 성공
                        man.push({ni,nj});
                        cout << step+1 << '\n';
                        loop = false;
                        break;
                    }
                    if (visit[ni][nj] <= step && visit[ni][nj] != 0 ) continue;
                    if ( board[ni][nj] == '*' || board[ni][nj] == '#') continue; // 막히면 패스
                    visit[ni][nj] = step + 1;
                    man.push({ni,nj});
                }
                man.pop();

                if (man.empty() && loop == true) {
                    // 상근이 갈 곳 없어서 사망각
                    // 상근이는 불이 붙을 곳으로 이동 할 수 없다.
                    // 상근이가 불에 죽었다면 불이 붙을 곳에 있었는데 이동할 수 없는 상황일 것이다.
                    cout << "IMPOSSIBLE" << '\n';
                    loop = false;
                    break;
                }
            }

        }
    }  // 테스트 순회 끝
}

insightn777 4년 전 0

board

visit

배열 앞에 static 을 붙여주었더니 해결되었습니다.

jung2381187 4년 전 0

board와 visit를 전역변수로 빼는 것도 한 가지 방법이죠

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

문제

문제

출처

ICPC

메모리 초과인데 이유를 모르겠습니다

insightn777 4년 전 0

insightn777 4년 전 0

jung2381187 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말