글 읽기 - 한번만 도와 주세요...ㅠㅠ

juju22 6년 전 0

어디가 틀린걸까요 ㅠㅠㅠ

5 5

.....

#*#..

#.@.#

###..

output: 3

불먼저 이동하고 상근이 이동하도록 구현 했는데 채점하면 틀린답니다 ㅠㅠㅠ

어디서 잘못 생각한걸까요 ㅠㅠ

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

using namespace std;

struct State{
    
    short u;
    short v;
    short time;
    
    State(short a = 0, short b = 0, short c = 0){
        u = a;
        v = b;
        time = c;
    }
    void set(short a, short b, short c = 0){
        u = a;
        v = b;
        time = c;
    }
};
int bfs(vector<vector<char>> &map, queue<State> &sq, queue<State> &fq, int &H, int &W){
    
    State cur;
    short u, v, nu, nv, time = 0, size;
    short du[4] = {0, 0, 1, -1};
    short dv[4] = {1, -1, 0, 0};

    while(!sq.empty())
    {

        // 불 이동
        size = (short)fq.size();
        while(size--)
        {
            cur = fq.front();
            fq.pop();
            u = cur.u;
            v = cur.v;
            
            for(short d = 0; d < 4; d++){
                nu = u + du[d];
                nv = v + dv[d];
                if(nu < 0 || nu >= H || nv < 0 || nv >= W || map[nu][nv] == '#' || map[nu][nv] == '*') continue;
                
                map[nu][nv] = '*';
                cur.set(nu, nv);
                fq.push(cur);
            }
        }
        
        // 상근이 이동
        size = (int)sq.size();
        while (size--) {
            
            cur = sq.front();
            sq.pop();
            u = cur.u;
            v = cur.v;
            time = cur.time;
            
            if(u < 0 || u >= H || v < 0 || v >= W) return time; // 탈출 조건
            
            for(short d = 0; d < 4; d++)
            {
                nu = u + du[d];
                nv = v + dv[d];
                
                if(nu < 0 || nu >= H || nv < 0 || nv >= W) return time + 1; // 탈출 조건
                if(map[nu][nv] == '#' || map[nu][nv] == '*' || map[nu][nv] == 'v') continue;
//                cout << nu << ' '<< nv  << endl;
                map[nu][nv] = 'v'; // visit 체크
                cur.set(nu, nv, time + 1);
                sq.push(cur);
            }
        }
    }
    
    return -1;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    
    ios::sync_with_stdio(false);
    short T;
    cin >> T;
    
    while (T--)
    {
        int H, W, ans;
        
        cin >> W >> H;
        
        vector<vector<char>> map(H + 1, vector<char>(W + 1));
        
        State cur;
        
        queue<State> sq, fq;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                
                cin >> map[i][j];
                
                if(map[i][j] == '*')
                {
                    cur.set(i, j);
                    fq.push(cur);
                }
                else if(map[i][j] == '@'){
                    map[i][j] = '.';
                    cur.set(i, j);
                    sq.push(cur);
                }
            }
        }
        
        ans = bfs(map, sq, fq, H, W);
        
        if(ans == -1) cout << "IMPOSSIBLE" << endl;
        else cout << ans << endl;
    }
    return 0;
}

djm03178 6년 전 1

short (2바이트) 안에 해결된다는 보장이 없습니다.

1000x1000칸에 지그재그로 길을 만들면 수십만 초 이상이 걸립니다.

아주 큰 배열을 만들어서 메모리를 정말로 반이라도 아껴야 하는 상황이 아니라면, 웬만하면 int를 쓰시길 권장합니다.

juju22 6년 전 0

아.. ㅠㅠ 메모리 초과나서 다 바꿨던게 문제였네요 ㅠㅠㅠ

알고리즘 문제인줄알고 엄청 헤메고 있었는데

읽어주셔서 정말 감사합니다 ㅠㅠㅠㅠㅠ!!!

메모리 초과가 난다면 십중팔구는 자료형의 크기를 줄이는 것으로 해결되지 않는 문제입니다. 자신의 알고리즘이 실제로 얼마의 메모리를 요구할지 생각해보고 그 알고리즘이 요구하는 공간복잡도를 구해보면 대략 어느 정도 메모리가 필요할지 예측할 수 있습니다. 공간복잡도에 문제가 없음에도 메모리 초과가 난다면 어딘가 중복해서 큐에 원소가 들어간다거나 무한루프에 걸려 빠져나오지 못하는 곳이 있다고 의심해야 됩니다.

juju22 6년 전 0

아 그렇군요!!! 자료형의 문제가 아닌 상근이 visit 체크하는 곳이나 불 번지는 부분에서 착오가 있었던거 같군요. 정말 감사합니다 !!

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

문제

문제

출처

ICPC

한번만 도와 주세요...ㅠㅠ

juju22 6년 전 0

djm03178 6년 전 1

juju22 6년 전 0

djm03178 6년 전 1

juju22 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말