[알고리즘/C++] 프로그래머스 - 석유 시추 (BFS)

🔽 정확성 통과 / 효율성 실패

✏️ 풀이 과정
저번 카카오프렌즈 컬러링북에서 사용했던 방식을 사용해서 풀었다.
하지만 효율성에서 시간초과의 늪에 빠졌다..

int solution(vector<vector<int>> land)
{
    int n = land.size(), m = land[0].size();
    vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    vector<vector<bool>> visit (n, vector<bool>(m, false));
    int area = 0, maxArea = 0;

    for (int j = 0; j < m; ++j)
    {
        fill( visit.begin(), visit.end(), vector<bool>(m, false) );

        for (int i = 0; i < n; ++i)
        {
            if (land[i][j] == 1 && visit[i][j] == false)
            {
                queue<pair<int, int>> waiting;
                waiting.push({i, j});
                visit[i][j] = true;
                area++;

                while (waiting.empty() == false)
                {
                    pair<int, int> curr = waiting.front();
                    waiting.pop();

                    for (int d = 0; d < dir.size(); ++d)
                    {
                        pair<int, int> next = {curr.first + dir[d].first, curr.second + dir[d].second};

                        if (next.first < 0 || next.first >= n || next.second < 0 || next.second >= m)   continue;
                        if (visit[next.first][next.second] == true)     continue;
                        if (land[next.first][next.second] == 0 || land[next.first][next.second] != land[curr.first][curr.second])     continue;

                        area++;
                        waiting.push(next);
                        visit[next.first][next.second] = true;
                    }
                }
            }
        }

        maxArea = max(maxArea, area);
        area = 0;
    }

    return maxArea;
}

🔽 통과 코드

풀이 과정
visit을 for문이 돌 때 마다 초기화 하는 과정이 시간초과의 원인인것 같아서
해당부분을 지우고 테스트했더니 시간초과가 나지 않았다.
그럼 전체 land를 한번 도는 것은 문제가 없다는 뜻이므로 처음 돌 때 영역마다 index를 지정했다.
이후 map에 <index, size>로 정보를 저장하고, 열마다 만나는 index 값을 set에 저장해 영역의 크기를 더할 수 있게 했다.

int solution(vector<vector<int>> land)
{
    int n = land.size(), m = land[0].size();
    vector<pair<int, int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    vector<vector<int>> area(n, vector<int>(m, 0));
    int areaSize = 0, areaIndex = 1;
    map<int, int> areaInfo;

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (land[i][j] == 1 && area[i][j] == 0)
            {
                queue<pair<int, int>> waiting;
                waiting.push({i, j});
                area[i][j] = areaIndex;
                areaSize++;

                while (waiting.empty() == false)
                {
                    pair<int, int> curr = waiting.front();
                    waiting.pop();

                    for (int d = 0; d < dir.size(); ++d)
                    {
                        pair<int, int> next = {curr.first + dir[d].first, curr.second + dir[d].second};

                        if (next.first < 0 || next.first >= n || next.second < 0 || next.second >= m)   continue;
                        if (area[next.first][next.second] != 0)     continue;
                        if (land[next.first][next.second] == 0 || land[next.first][next.second] != land[curr.first][curr.second])     continue;

                        areaSize++;
                        waiting.push(next);
                        area[next.first][next.second] = areaIndex;
                    }
                }
            }

            if (areaSize > 0)
            {
                areaInfo[areaIndex] = areaSize;
                areaIndex++;
                areaSize = 0;
            }
        }
    }

    int cnt = 0, answer = 0;
    set<int> ids;
    for (int j = 0; j < m; ++j)
    {
        for (int i = 0; i < n; ++i)
        {
            if (area[i][j] != 0 && ids.find(area[i][j]) == ids.end())
            {
                ids.insert(area[i][j]);
                cnt += areaInfo[area[i][j]];
            }
        }

        answer = max(answer, cnt);
        cnt = 0;
        ids.clear();
    }

    return answer;
}

---

아쉬운 점
좀 더 깔끔하게 정리할 수 있는 방법이 있을 것 같은데 아쉽다.