글 읽기 - 메모리 초과로 통과 못하는 가운데.. 고수님의 조언을 구합니다.

yongjunleeme 2년 전 0

메모리 초과가 나옵니다 ㅠ ㅠ

함수 호출과 큐의 크기를 최소화하라는 조언이 있던데.. 어떻게 해야 할 지 뾰족한 수가 떠오르지 않아서

고수님의 조언을 구합니다.. !

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
const int MX = 1502;
int r, c, lx, ly, cnt = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int vis[MX][MX];
int visted[MX][MX];
string board[MX];
bool isPossible = false;
queue <pair<int, int>> Q;
queue <pair<int, int>> Q2;
queue <pair<int, int>> LQ;
queue <pair<int, int>> LQ2;


bool OOB(int a, int b){
    return a < 0 || a >= r || b < 0 || b >= c;
}


int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;
    for(int i = 0; i < r; i++) cin >> board[i];
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(board[i][j] == 'L'){
                lx = i;
                ly = j;
            
            }
            else if(board[i][j] == '.') Q.push({i, j});
        }
    }
    
    LQ.push({lx, ly});
    board[lx][ly] = '.';
    vis[lx][ly] = 1;
    
    while(!isPossible){
        
        //얼음 녹이기
        while(!Q.empty()){
            auto cur = Q.front(); Q.pop();
            visted[cur.X][cur.Y] = 1;
            for(int dir = 0; dir < 4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(OOB(nx, ny) || visted[nx][ny]) continue;
                
                if(board[nx][ny] == 'X') Q2.push({nx, ny});
                visted[nx][ny] = 1;
            }
        }
        
        while(!Q2.empty()){
            auto cur = Q2.front(); Q2.pop();
            board[cur.X][cur.Y] = '.';
            Q.push({cur.X, cur.Y});
        }
        cnt++;
        
        //백조 찾기
        while(!LQ.empty()){
            auto cur = LQ.front(); LQ.pop();
            vis[cur.X][cur.Y] = 1;
    
            for(int dir = 0; dir < 4; dir++){
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if(OOB(nx, ny) || vis[nx][ny]) continue;
                if(board[nx][ny] == 'X'){
                    LQ2.push({cur.X, cur.Y});
                    continue;
                }
                else if(board[nx][ny] == 'L'){
                    isPossible = true;
                    break;
                }
                vis[nx][ny] = 1;
                LQ.push({nx, ny});
            }
        }
        while (!LQ2.empty()){
            auto cur = LQ2.front(); LQ2.pop();
            LQ.push({cur.X, cur.Y});
        }
    }
    cout << cnt;
}

hgo99 1년 전 1

board[i][j]가 물이 아니라 백조일때도 Q에 푸쉬해줘야합니다. if(board[i][j] == '.'|| board[i][j] == 'L') Q.push({i, j});로 바꿔주세요

yongjunleeme 1년 전 0

조언 감사드립니다!

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

문제

문제

출처

ICPC

메모리 초과로 통과 못하는 가운데.. 고수님의 조언을 구합니다.

yongjunleeme 2년 전 0

hgo99 1년 전 1

yongjunleeme 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말