[Algorithm]Baekjoon 16946 :: 벽 부수고 이동하기 4

https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4

 
 
using namespace std;
 
 
int n, m;
int arr[1001][1001] = { 0 };
int visitedWalls[1001][1001] = { 0 };
int dirs[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int turn = 0;
 
void BFS(int y, int x)
{
    ++turn;
    queue<pair<int,int>> q;
    vector<pair<int, int>> walls;
 
    q.push({ y,x });
    int count = 1;
 
    while (!q.empty())
    {
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dirs[i][0];
            int nextX = curX + dirs[i][1];
 
            if (nextY < 0 || nextY == n) continue;
            if (nextX < 0 || nextX == m) continue;
            if (arr[nextY][nextX] == -1) continue;
            if (visitedWalls[nextY][nextX] == turn) continue;
 
            if (arr[nextY][nextX] > 0) // 벽이면
            {
                visitedWalls[nextY][nextX] = turn;
                walls.push_back({ nextY,nextX });
            }
            else if (arr[nextY][nextX] == 0) // 빈공간이면
            {
                arr[nextY][nextX] = -1;
                ++count;
                q.push({ nextY,nextX });
            }
        }
    }
 
    for (int i = 0; i < walls.size(); ++i)
    {
        arr[walls[i].first][walls[i].second] += count;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        string s;
        cin >> s;
 
        for (int j = 0; j < m; ++j)
        {
            arr[i][j] = s[j] - '0';
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (arr[i][j] == 0)
            {
                arr[i][j] = -1;
                BFS(i, j);
            }
        }
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (arr[i][j] == -1)
            {
                printf("%d", 0);
            }
            else printf("%d", arr[i][j] % 10);
        }
 
        printf("\n");
    }
}

 

문제에서는 각 벽을 부쉈을 때 탐색가능한 모든 칸을 구해야한다고 되어있다.

그렇다고 각 벽을 기준으로 전부 BFS를 돌리면 시간초과에 걸린다. 1000*1000이라서 대충 벽 1만개가 띄엄띄엄 배치되어있다고 치면 10000 * 990000이라서 시간복잡도가 너무 커진다.

 

그래서 역발상으로, 빈공간을 기준으로 탐색을 진행한다. 빈공간을 탐색하면서 어떤 벽을 만난다면, 해당벽을 기준으로 출발했을 때도 빈공간을 탐색할 수 있다는 것이다.

그래서 빈공간을 기준으로 모든 빈공간을 탐색할건데, 도중에 벽을 만나면 해당벽의 위치를 따로 저장해놓는다.

이후 모든탐색을 마친 후에, 벽의 위치를 저장한 컨테이너를 순회하면서 해당 벽의위치에 빈공간의카운팅값을 누적시켜준다.

그냥 처음 인풋배열인 arr에 바로 누적시켜주면 된다.

 

한가지 주의해야 할 점은, 0인 공간(빈 공간)을 탐색하며 카운팅하는 과정에서 벽을 만나면 따로 저장하라했는데, 저장 후에 해당벽은 이미 저장했다고 방문표시를 해놔야 한다. 안그러면 다른 노드에서 뻗어가는 과정에서 한번 더 저장해버리기 때문에, 실제 값보다 더 누적되버린다.

그렇다고 이거 방문표시한다고 BFS함수내에서 지역변수로 visited[1001][1001]을 해서 체크한다? 

-> 통과는 한다. 근데 시간이 더 걸린다. 매 BFS수행마다 1001 * 1001 크기의 배열을 초기화시켜야 하기 때문이다.

     그러니 그냥 전역변수로 visited 해서 알아서 중복저장 안되게 방문검사하면 된다.

     나같은경우는 매 BFS마다 turn이라는 flag값을 줘서 벽을 만나면 turn을 저장시킨 다음, 이후 다른곳에서 동일한 벽을 만났을 때 해당좌표에 turn값이 들어있으면 그냥 지나치게 했다.

 

 

 

 

밑의 1796ms가 BFS내부에 visited를 만들어서 제출한 코드고, 108ms가 전역으로 visited해서 제출한 코드다.