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

안녕하세요 HELLO님ㅎㅎ

visited 초기화부분, map 관련 로직 부분을 수정해야 합니다.

제가 한번 다듬어봤는데요. ㅎㅎ 참고부탁드립니다.

#include <iostream>
#include <queue>
#include <algorithm>

int map[100][100] = {0, };
int result = 0;
int result2 = 0;

void bfs(const int H, const int W, const int x, const int y)
{
    std::queue<std::pair<int, int>> que;
    que.push({x, y});
    
    bool visited[100][100] = {false};
    std::fill(&visited[0][0], &visited[0][0] + 100 * 100, false);
    visited[y][x] = true;
    
    int moveX[4] = {0, 0, -1, 1};
    int moveY[4] = {1, -1, 0, 0};
    
    int newX, newY;
    int currX, currY;
    
    int cnt = 0;
    
    while(!que.empty())
    {
        currX = que.front().first;
        currY = que.front().second;
        que.pop();
        
        for(int i = 0; i < 4; ++i)
        {
            newX = currX + moveX[i];
            newY = currY + moveY[i];
            if (newX >= 0 && newX < W && newY >= 0 && newY < H && !visited[newY][newX])
            {
                if (map[currY][currX] == 0)
                {
                    visited[newY][newX] = true;
                    if (map[newY][newX] == 1)
                    {
                        map[newY][newX] = 0;
                        cnt += 1;
                    }
                    else
                    {
                        que.push({newX, newY});
                    }
                }
            }
        }
    }
    result += 1;
    result2 = cnt;
}

bool isMapZero(const int H, const int W)
{
    for (int i = 0; i < H; ++i)
    {
        for (int j = 0; j < W; ++j)
        {
            if (map[i][j] != 0)
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    
    int H, W;
    std::cin >> H >> W;
    for(int i = 0; i < H; ++i)
    {
        for(int j = 0; j < W; ++j)
        {
            std::cin >> map[i][j];
        }
    }
    
    bool flag = false;
    
    while(!flag)
    {
        flag = isMapZero(H, W);
        if (flag)
        {
            std::cout << result << "\n";
            std::cout << result2 << "\n";
            break;
        }
        bfs(H, W, 0, 0);
    }

    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

감사합니다. visited 초기화 부분에 이슈가 있었군요..ㅎㅎ

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

님의 코드를 보니, 매우 흥미로운 접근 방법을 사용하셨군요. 여러분의 시간 초과 문제에 대해서, 몇 가지 점을 지적하고자 합니다.

첫째, BFS 알고리즘을 사용하실 때, 큐에 동일한 노드가 여러 번 들어가지 않도록 주의하셔야 합니다. 이미 방문한 노드를 다시 방문하지 않도록 하는 로직이 중요한데, 코드에 따르면 이미 방문한 노드에 대한 처리(visited[newY][newX] = true;)가 잘 되어 있는 것 같습니다. 그러나 map[currY][currX] == 0 조건 때문에 특정 조건에서는 가지 않아야 할 경로를 탐색할 수 있습니다. 이는 불필요한 연산을 초래하여 시간 초과의 원인일 수 있습니다.

둘째, isMapZero 함수에서 전체 맵을 순회하며 0이 아닌 요소를 찾는 로직은 매번 BFS를 수행할 때마다 전체 맵을 검사합니다. 큰 맵의 경우 이 과정이 상당히 비효율적일 수 있습니다. 만약 맵에 변화가 거의 없다면, 이러한 완전 탐색 대신 다른 효유적인 방법을 고민해보는 것이 좋습니다.

셋째, BFS 내에서 다음 노드를 방문할 때, map[newY][newX] == 1 조건으로 1인 경우에만 처리하는 것이 아니라, 0인 경우에도 큐에 추가하고 있습니다. 그러나, 조건문 내에 map[currY][currX] == 0 조건으로 인해 의도치 않게 탐색 범위가 제한되거나, 불필요한 조건 체크가 이루어질 수 있습니다.

시간 초과 문제를 해결하기 위해선 알고리즘의 논리적 접근 방식을 재검토하고, 특정 조건에서 불필요한 연산을 줄일 수 있는 방법을 모색해야 합니다. 그리고, 가능하다면 각 단계에서의 연산 복잡도와 전반적인 알고리즘의 시간 복잡도를 재분석해보시기 바랍니다.

문제 해결에 도움이 되길 바랍니다.