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

안녕하세요 ㅎㅎ

로직자체는 괜찮습니다. ㅎㅎ

다만 q에 push하면서 visited 처리를 해야 합니다.

-> 여기서는 vv가 0으로 바뀌는 부분이겠죠?

이부분을 바꿔야 합니다.

q에다 push를 할 때 그런 처리를 안하고 pop을 할 때 하게 되면 중복된 정점을 많이 방문 -> q에 많은 정점이 들어가게 됨 -> 메모리초과가 되게 됩니다.

예를 들어 q에 1, 1, 1, 1 이 쌓였는데 계속해서 로직 수행하고 -> 나중에 1을 뺐을 때 방문처리한다고 보시면 됩니다.

제가 좀 다듬어봤는데 이렇게 해보시겠어요?

include 정리 + 일부코드 정리

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

using namespace std;

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

void bfs(vector<vector<int>> &vv, int x, int y)
{
    queue<pair<int, int>> q;
    q.push({x, y});
    vv[y][x] = 0;

    while (!q.empty())
    {
        int curX = q.front().first;
        int curY = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int nx = curX + dx[i];
            int ny = curY + dy[i];

            if (nx >= 0 && ny >= 0 && nx < vv[0].size() && ny < vv.size() && vv[ny][nx] == 1)
            {
                q.push({nx, ny});
                vv[ny][nx] = 0;
            }
        }
    }
}

int solution(vector<vector<int>> &vv, const vector<pair<int, int>> &orders)
{
    int answer = 0;

    for (const auto &p : orders)
    {
        int x = p.first;
        int y = p.second;
        if (vv[y][x] == 1)
        {
            bfs(vv, x, y);
            answer++;
        }
    }
    return answer;
}

int main()
{
    vector<int> answer;
    size_t T;
    cin >> T;
    while (T--)
    {
        int M, N, K;
        cin >> M >> N >> K;
        vector<vector<int>> vv(N, vector<int>(M, 0));
        vector<pair<int, int>> orders;

        for (int i = 0; i < K; ++i)
        {
            int x, y;
            cin >> x >> y;
            vv[y][x] = 1;
            orders.push_back({x, y});
        }

        answer.push_back(solution(vv, orders));
    }
    for (const int result : answer)
        cout << result << '\n';

    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

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

geonwlee22님의 질문에 대한 답변으로, “백준 1012 유기농 배추 문제”와 관련된 유사한 컨텍스트를 가진 정보를 찾았습니다. 질문 내용에 기반해 제공되는 코드에서 메모리 초과 문제를 겪고 계신 것으로 이해됩니다. 이와 유사한 상황에서의 문제 해결 방법을 제시한 기존 질문&답변 정보를 안내드리겠습니다.

동일한 코스 내에서 배추를 활용한 문제 해결에 대한 질문이 있었고, 해당 질문에서도 메모리 초과가 아닌 다른 문제 (예를 들어, 배열 초기화 문제)에 집중하고 있지만, 코드 최적화 관련된 조언이 포함되어 있어 도움이 될 것입니다.

• 질문: “백준 1012 유기농 배추 문제”에서 질문자가 메모리 초과가 아닌 패스가 안될 때의 문제를 상담했습니다. 질문에 대한 답변에서는 코드의 특정 부분(예: 초기화 부분)이 잘못되었음을 지적하고 있습니다. 해당 답변에 따르면 질문자의 코드에서 입출력 부분과 초기화 부분에 있어 수정이 필요했으며, 이와 비슷한 상황에서의 진단 방법이나 고려사항이 geonwlee22님의 문제에도 도움이 될 수 있습니다.
  

본 답변에서 제시한 경우는 메모리 초과 문제에 대한 직접적인 해결 방법을 제공하지 않지만, BFS를 사용한 문제 해결 과정에서 고려해야 할 일반적인 코드 개선 방법에 대한 통찰을 얻으실 수 있을 것입니다.

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