[C++] 백준 10711번: 모래성

🔗 문제

10711번: 모래성

10711번: 모래성

 

🖍 풀이

 

문제의 조건

• 1 ≤ H, W ≤ 1,000
  • 💡 파도가 몇번 칠지도 모르는데 이 범위를 2차원 배열을 이중포문으로 접근하는 건 TLE 가능성이 높다

 

그래서 모래가 있는 위치를 기준으로 BFS 했지만 시간 초과 🙂

시간 초과에 늪에 빠져서 🔗여기 에서 도움을 받았다.

 

처음엔 뭔 소리인지 모르겠어서 디버깅했더니 기존 코드의 실패 원인과 풀이 방법도 이해할 수 있었다.

 

 

📋 시간 초과 원인과 소스 코드

 

시간 초과 원인

 

모래가 있는 위치를 파도가 칠때마다 반복적으로 8방을 확인하여 빈 곳을 찾아내는 것이 문제다.

• 과정: [1][1]에 모래가 있어서 팔방의 빈 모래 개수를 세었다.
• 결과: 모래가 없어지지 않았기 때문에 다음 탐색 대상이다.

이 과정에서 똑같은 위치의 모래의 팔방을 보고 또 보고 계~~속 반복되는게 시간 초과 원인이다.

 

소스 코드

 

#include <iostream>
#include <queue>

typedef std::pair<int, int> pii;

const int MAX = 1000 + 1;
const int dx[8] = {0, 0, 1, -1, -1, 1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

std::queue<pii> rest, check; // 모래가 있는 위치, 모래가 없는 위치 
int map[MAX][MAX] = {0, };
int W, H;

void input()
{
    char c;
    
    std::cin >> W >> H;

    for(int i=0; i<W; ++i)
    {
        for(int j=0 ;j<H; ++j)
        {
            std::cin >> c;
            if(c != '.') 
            {
                map[i][j] = c - '0';
                rest.push({i, j});
            }
        }
    }
}

bool isValid(const int x, const int y)
{
    if(x<0 || x>=W || y<0 || y>=H)
        return false;

    return true;
}

int getEmpty(const int x, const int y)
{
    int sum = 0;

    for(int d=0; d<8; ++d)
    {
        if(isValid(x + dx[d], y+ dy[d]) 
         && (map[x+dx[d]][y+dy[d]]==0))
            ++sum;
    }

    return sum;
}

int solve()
{
    int answer = 0;

    while(!rest.empty())
    {
        int qSize = rest.size();
        while(qSize--)
        {
            int x = rest.front().first;
            int y = rest.front().second;
            rest.pop();
            
            if(map[x][y] == 9 || map[x][y] > getEmpty(x, y))
                rest.push({x, y});
            else
                check.push({x, y});
        }

        if(check.empty())
            return answer;

        while(!check.empty())
        {
            map[check.front().first][check.front().second] = 0;
            check.pop();
        }
        ++answer;
    }

    return answer;
}

int main()
{
    input();
    
    std::cout << solve();

    return 0;
}

 

 

 

모래가 없는 위치를 기준으로 문제를 풀어야 한다.

모래가 없는 곳에서 8방으로 모래가 있다면 그 모래를 깍는다.

1. 일단 첫 파도에 시키는대로 모래가 있으면 —map[x][y]시킨다.
2. 모래가 없어지는 위치가 생기는데 그 친구를 큐에 넣는다. 모래가 없는 부분이 되었으니까..!

여기까지는 쉽게 이해할 수 있었다.

근데 감소시키면 다음 파도에 논리 오류로 사라지는거 아닌가 고민이 됐었다.

하지만 빈 곳이라고 계속 queue에 넣는 것이 아닌 새로 생긴 빈 곳만 넣는다는 점에 주목해야한다.

이미 파도로 한번 모래를 깍은 기존 파도 구역은 queue에 넣지 않기 때문에 중복으로 모래를 깍는 일은 없다.

(내 코드 한번만 디버깅하면 이해가 될 것)

 

당연히 상대적으로 새로 생긴 빈 곳의 위치가 적으니 시간 초과에서 벗어날 수 있었다.

 

💾  소스

#include <iostream>
#include <queue>

typedef std::pair<int, int> pii;

const int MAX = 1000 + 1;
const int dx[8] = {0, 0, 1, -1, -1, 1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

std::queue<pii> check;
int map[MAX][MAX] = {0, };
int W, H;

void input()
{
    char c;
    
    std::cin >> W >> H;

    for(int i=0; i<W; ++i)
    {
        for(int j=0 ;j<H; ++j)
        {
            std::cin >> c;
            
            if(c != '.') 
                map[i][j] = c - '0';
            else
                check.push({i, j});
        }
    }
}

bool isValid(const int x, const int y)
{
    if(x<0 || x>=W || y<0 || y>=H)
        return false;

    return true;
}

int solve()
{
    int answer = 0;

    while(!check.empty())
    {
        int qSize = check.size();
        while(qSize--)
        {
            int nowX = check.front().first;
            int nowY = check.front().second;
            check.pop();
            
            for(int d=0; d<8; ++d)
            {
                int x = nowX + dx[d];
                int y = nowY + dy[d];

                if(isValid(x, y) && map[x][y] > 0)
                {
                    if(--map[x][y] == 0)
                        check.push({x, y});
                }
            }
        }
                
        ++answer;
    }

    return answer-1;
}

int main()
{
    input();

    std::cout << solve();

    return 0;
}