글 읽기 - 도대체 왜 메모리 초과인가요???

sctm1219 1년 전 0

https://www.acmicpc.net/board/...

이 경우도 해봤는데 98이 나왔습니다.

진짜 아무리 생각해도 메모리 초과 되는 이유를 모르겠습니다. 도움 부탁드려요 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

int r, c, map[50][50], dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
bool visit[50][50];
pair<int, int> d, s;

queue<pair<pair<int ,int>, int>> q;

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

    cin>>r>>c; string str; bool check = false; int time;
    for(int i=0; i!=r; i++) {
        cin>>str; 
        for(int j=0; j!=c; j++) {
            if(str[j] == '*') q.push({{i, j}, 0});
            else if(str[j] == 'D') {map[i][j] = 0; d.first = i; d.second = j;}
            else if(str[j] == 'S') {map[i][j] = -1; s.first = i; s.second = j;}
            else map[i][j] = -1;
        }
    }
    while(!q.empty()){
        int x = q.front().first.first, y = q.front().first.second;
        int t = q.front().second;
        map[x][y] = t;
        q.pop();
        for(int i=0; i!=4; i++){
            int tx = x + dx[i], ty = y + dy[i];
            if(tx<0||ty<0||tx>=r||ty>=c) continue;
            if(map[tx][ty]>=0) continue;
            q.push({{tx, ty}, t + 1});
        }
    }
    q.push({{s.first, s.second}, 0});
    visit[s.first][s.second] = true;
    while(!q.empty()){
        if(check) break;
        int x = q.front().first.first, y = q.front().first.second;
        int t = q.front().second;
        q.pop();
        for(int i=0; i!=4; i++){
            int tx = x + dx[i], ty = y + dy[i];
            if(tx<0||ty<0||tx>=r||ty>=c) continue;
            if(tx==d.first&&ty==d.second) {
                check = true; time = t+1;
                break;
            }
            if(visit[tx][ty]) continue;
            if(map[tx][ty]>=0&&map[tx][ty]<=t+1) continue;
            q.push({{tx, ty}, t + 1});
            visit[tx][ty] = true;
        }
    }
    if(check) cout<<time;
    else cout<<"KAKTUS";

    return 0;
}

adung7 1년 전 1

우선 로직상 X의 관한 처리가 없습니다 따라서 예제 3번이 KAKTUS가 나오게 됩니다

또, 31번째줄에서 큐에서 원소를 꺼내고 물 퍼지는 시간을 map에 넣으시는데 이럴 경우 이 정보가 큐에 꺼내기 전까지는 갱신 되지 않으므로

큐에 남은 원소들이 방문 한적이 없다고 판단하여 계속 큐에 원소들을 넣게될것입니다

이 둘을 처리해주세요

sctm1219 1년 전 0

정말 감사합니다 이 쉬운 걸 놓치고 있었다니...ㅜㅜ

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

문제

문제

출처

ICPC

도대체 왜 메모리 초과인가요???

sctm1219 1년 전 0

adung7 1년 전 1

sctm1219 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말