인프런 커뮤니티 질문&답변

안녕하세요 지성님 ㅎㅎ

제 생각에는 이부분 때문에 특정반례에서 fire bfs가 방문한 지점을 다시 방문하는 자주 로직이 발생 -> 메모리초과가 나는 것 같습니다.

    for (auto f_point : f_points)
    {
      
        q.push(f_point);
        fire[f_point.first][f_point.second] = 1;
        while (!q.empty())

fire[y][x] + 1 > fire[ny][nx]

예를 들어

이런 입력의 경우 다음과 같은 출력을 가지게 됩니다.

입력
6 5
FFFFF
#...#
FFFFF
#...#
#J..#
#####
 
출력
0 : 0
0 : 1
1 : 0
0 : 2
1 : 1
1 : 1
2 : 0
0 : 3
1 : 2
1 : 2
2 : 1
1 : 2
2 : 1
2 : 1
3 : 0
0 : 4
1 : 3
1 : 3
2 : 2
1 : 3
2 : 2
2 : 2
3 : 1
1 : 3
2 : 2
2 : 2
3 : 1
2 : 2
3 : 1
3 : 1
4 : 0
1 : 4
2 : 3
2 : 3
2 : 3
3 : 2
2 : 3
2 : 3
3 : 2
2 : 3
3 : 2
3 : 2
4 : 1
2 : 3
2 : 3
3 : 2
2 : 3
3 : 2
3 : 2
4 : 1
2 : 3
3 : 2
3 : 2
4 : 1
3 : 2 
...
4
3
4
4
IMPOSSIBLE

디버깅 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
char board[1005][1005];

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int fire[1005][1005];
int jihun[1005][1005];

int y, x;
vector<pair<int, int>> f_points;
pair<int, int> j_point;

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

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 'F')
                f_points.push_back({i, j});
            if (board[i][j] == 'J')
                j_point = {i, j};
        }
    }
    queue<pair<int, int>> q;
    for (auto f_point : f_points)
    {
      
        q.push(f_point);
        fire[f_point.first][f_point.second] = 1; 
        while (!q.empty())
        {
            tie(y, x) = q.front();
            cout << y << " : " << x << "\n";
            q.pop();
            for (int dir = 0; dir < 4; dir++)
            {
                int ny = y + dy[dir];
                int nx = x + dx[dir];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m)
                    continue;
                if ((board[ny][nx] == '#' || fire[y][x] + 1 > fire[ny][nx]) && fire[ny][nx] != 0)
                    continue;
                fire[ny][nx] = fire[y][x] + 1;
                q.push({ny, nx});
            }
        }
    }

    q.push(j_point);
    jihun[j_point.first][j_point.second] = 1;
    while (!q.empty())
    {
        tie(y, x) = q.front();
        cout << y << "\n";
        q.pop();
        for (int dir = 0; dir < 4; dir++)
        {
            int ny = y + dy[dir];
            int nx = x + dx[dir];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m)
            {
                cout << jihun[y][x];
                return 0;
            }

            if (board[ny][nx] == '#' || jihun[ny][nx] != 0)
                continue;
            if (jihun[y][x] + 1 > fire[ny][nx] && fire[ny][nx] != 0)
                continue;
            jihun[ny][nx] = jihun[y][x] + 1;
            q.push({ny, nx});
        }
    }
    cout << "IMPOSSIBLE";
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다.

김지성님, 메모리 초과 문제로 고민하고 계신 것으로 보입니다. 메모리 초과는 프로그램이 할당된 메모리보다 많은 메모리를 사용할 때 발생합니다. 이는 종종 불필요한 큰 배열을 선언하거나, 깊이가 깊은 재귀호출로 인해 발생할 수 있습니다. 또한, 적절하지 않게 메모리를 할당하거나 해제하지 않는 경우에도 종종 메모리 초과가 발생할 수 있습니다.

유사한 경우의 질문에 대한 답변으로, 아래의 링크를 참고하실 수 있습니다:

• 3-D 불! 메모리 초과 질문 있습니다.
  
• 3-D 메모리 초과
  
• 4179 불! 3-D 질문합니다
  

위 링크들은 모두 메모리 초과와 관련된 질문에 대한 지식공유자 큰돌님의 답변을 포함하고 있습니다. 해당 답변에서는 메모리 초과를 일으키는 코드의 예시와 그 해결방안을 제시하고 있으니 유사한 문제를 겪고 계신다면 많은 도움이 될 것입니다.

질문자님의 코드를 확인하지 못해 구체적인 해결책을 제공하기는 어렵지만, 메모리 초과 문제를 해결하기 위해서는 큐에 넣는 요소의 수를 줄이거나, 배열의 크기를 적절히 조정하는 등의 방법을 시도하실 수 있습니다. 또한, 이미 방문했던 위치를 다시 방문하지 않도록 처리하는 로직이 있는지 확인하고, 시간복잡도 및 공간복잡도를 개선할 수 있는 방식을 고려해보시기 바랍니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.