백준 3055 / 탈출

BFS 연습문제

어렵다. 문제를 풀기 전 캐치해야될 것

고슴도치가 움직이기 전 물이 먼저 움직여야한다. (물의 4방향 탐색이 끝나야한다)

그래서 풀어봤더니

런타임 에러..

비주얼 스튜디오에선 잘만 돌아가는데 백준에선 런타임 에러가 났다.

그 이유를 검색해보니

[원인]

배열에 할당된 크기를 넘어서 접근했을 때

전역 배열의 크기가 메모리 제한을 초과할 때

지역 배열의 크기가 스택 크기 제한을 넘어갈 때

0으로 나눌 때

라이브러리에서 예외를 발생시켰을 때

재귀 호출이 너무 깊어질 때

이미 해제된 메모리를 또 참조할 때

이 7가지 일이 발생했을 때 런타임 에러가 난다고 한다. 내 코드의 경우는 QUEUE가 비어있는데 계속 POP이나 FRONT 등 접근을 시도한 경우인 듯.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
 
using namespace std;
 
 
int main() {
 
    int n, m;
    char map[100][100];
    int wdist[100][100];
    int dist[100][100];
 
 
    queue<pair<int, int>>S;
    queue<pair<int, int>>S2;
    queue<pair<int, int>>water;
    queue<pair<int, int>>water2;
 
    int dx[] = { 0,0,1,-1 };
    int dy[] = { 1,-1,0,0 };
 
    int goalx;
    int goaly;
 
 
    //freopen("Text.txt", "r", stdin);
    cin >> n >> m;
 
 
 
    memset(wdist, -1, sizeof(wdist));
    memset(dist, -1, sizeof(dist));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            if (map[i][j] == 'S') {
                S.push(make_pair(i, j));
                dist[i][j] = 0;
            }
            if (map[i][j] == '*') {
 
                wdist[i][j] = 0;
                water.push(make_pair(i, j));
 
            }
            if (map[i][j] == 'D') {
                goalx = i; goaly = j;
            }
        }
    }
 
 
    if (!water.empty()) {
        while (!S.empty()) {
 
            if (water.empty()) {
 
                while (!S.empty()) {
                    int x, y;
                    x = S.front().first;
                    y = S.front().second;
                    S.pop();
 
                    for (int i = 0; i < 4; i++) {
                        int nx, ny;
                        nx = x + dx[i];
                        ny = y + dy[i];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                            if (map[nx][ny] == '.' && dist[nx][ny] == -1) {
                                dist[nx][ny] = dist[x][y] + 1;
                                S2.push(make_pair(nx, ny));
                            }
                            if (map[nx][ny] == 'D'&&dist[nx][ny] == -1) {
                                dist[nx][ny] = dist[x][y] + 1;
                                break;
                            }
                        }
                    }
                }
                S = S2;
                S2 = queue<pair<int, int>>();
 
 
                water = water2;
                water2 = queue<pair<int, int>>();
 
            }
            else {
                int wx, wy;
                wx = water.front().first;
                wy = water.front().second;
                water.pop();
 
                for (int i = 0; i < 4; i++) {
                    int nwx, nwy;
                    nwx = wx + dx[i];
                    nwy = wy + dy[i];
                    if (nwx >= 0 && nwx < n && nwy >= 0 && nwy < m) {
 
                        if (map[nwx][nwy] == '.' && wdist[nwx][nwy] == -1) {
 
                            wdist[nwx][nwy] = wdist[wx][wy] + 1;
                            map[nwx][nwy] = '*';
                            water2.push(make_pair(nwx, nwy));
                        }
                    }
                }
            }            
        }
    }
 
    else {
        while (!S.empty()) {
            int x, y;
            x = S.front().first;
            y = S.front().second;
            S.pop();
 
            for (int i = 0; i < 4; i++) {
                int nx, ny;
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (map[nx][ny] == '.' && dist[nx][ny] == -1) {
                        dist[nx][ny] = dist[x][y] + 1;
                        S.push(make_pair(nx, ny));
                    }
                    if (map[nx][ny] == 'D'&&dist[nx][ny] == -1) {
                        dist[nx][ny] = dist[x][y] + 1;
 
                    }
 
                }
            }
 
        }
    }
 
    if (dist[goalx][goaly] == -1) {
        cout << "KAKTUS";
    }
    else
        cout << dist[goalx][goaly];
 
}

아ㅇ

아 그리고 애초에 맵 상에 물이 없을 경우도 처리해줘야한다. 

////////////////////////////////////

ps. 다른 코드 해설보니까 물이 그 지점까지 이동하는 시간을 담아놓는 배열을 따로 만들어놓고

     고슴도치가 이동하는 시간과 비교하여 푸는 방법도 있다. 

나는 BFS를 2번 돌렸는데 효율이 그리 좋지 않은가 보다. 코드도 더럽다.