벽 부수고 이동하기 4

알고리즘 구분 : 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색,

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

벽을 부수고 이동할 수 있는 곳으로 변경한다.
그 위치에서 이동할 수 있는 칸의 개수를 세어본다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력
맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1
3 3
101
010
101
예제 출력 1
303
050
303
예제 입력 2
4 5
11001
00111
01010
10101
예제 출력 2
46003
00732
06040
50403

문제 풀이

처음 접근 방법

1) 입력 받을 당시, 벽에 대한 별도의 벡터를 생성하여 해당 좌표들을 저장해놓음
2) 해당 좌표들별로 dfs를 진행하여 해당 값을 result(2차원 배열)에 저장
3) 결과값 출력
위와 같이 접근하고자 하였으나, 입력 테스트 케이스들이 1000x1000인 상황에서 바둑판 배열로 벽과 빈 곳이 존재한다면, 해당 시간 복잡도는 O(r^2c^2)가 될 수 있어서 TLE가 될 것으로 판단했다.

위의 과정을 생각해보면서, 0인 자리에 대해서 한 번 확인했음에도 불구하고 다시 확인하는 절차를 거치는 것을 최소화시키는 것이 시간 복잡도를 줄일 수 있는 방법으로 생각했다.

두 번째 방법

0인 자리는 한 번 계산을 한 이후에, 계산된 값을 필요시마다 활용하는 방향으로 정했다.
1) 0인 자리에 대해 최대 갈 수 있는 거리에 대한 계산을 진행한다.
2) 벽에 대한 별도의 벡터를 생성한 것을 이용하여, 해당 위치를 기준으로 4 방향에 0인 자리가 있는 지 확인한다.
3) 확인이 되면 해당 0인 자리에서 갈 수 있는 곳들을 계산해놓은 값을 더해주는 방식으로 구현해보았다.
위와 같이 접근하는 경우, 문제의 두 번째 예제에서 중복되는 곳들을 계속 더해주게 되기 때문에, 해당 방식에서 중복 제거하는 과정이 추가적으로 필요했다.

정답 접근 방법

0인 자리들끼리 하나의 구역으로 간주하기로 하였다.
아래의 정답 소스 코드를 보면 areaNum 변수와 areaSize배열이 있는데, 이는 0인 자리에서 한 번에 움직일 수 있는 거리들을 묶어서 하나의 areaNum으로 구역을 정하고, 해당 구역의 크기에 대해 areaSize배열에 저장해놓도록 하였다.
그 이후, wallBfs()에서 set 컨테이너를 이용해 중복 제거를 했다.
wallBfs()의 중복 제거 방법은 아래의 사진과 같다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n, m, num;
vector<pair<int, int>> wall;
vector<pair<int, int>> space;
int graph[1001][1001];
int result[1001][1001];
int areaNum[1001][1001];
bool visited[1001][1001];
vector<int> areaSize;
void wallBfs(pair<int, int> now); // 1인 곳에서 bfs 결과 반환
void spaceBfs(pair<int, int> now); //0인 곳에서 bfs 결과 반환
void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char input;
            cin >> input;
            if(input == '1') {
                wall.push_back({i, j});
                graph[i][j] = 1;
            }
            else if(input == '0') {
                space.push_back({i, j});
                graph[i][j] = 0;
            }
        }
    }

    memset(areaNum, -1, sizeof(areaNum));

    solve();

    return 0;
}

void wallBfs(pair<int, int> now) {
    int nx, ny;
    set<int> search;
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};

    for(int i = 0; i < 4; i++) {
        nx = now.first + dx[i];
        ny = now.second + dy[i];

        if(0 > nx || nx >= n || 0 > ny || ny >= m) {
                continue;
        }

        if(graph[nx][ny] == 0) {
            if(search.find(areaNum[nx][ny]) == search.end()) {
                search.insert(areaNum[nx][ny]);
                result[now.first][now.second] += areaSize[areaNum[nx][ny]];
            }
        }
    }

    result[now.first][now.second]++;
    result[now.first][now.second] %= 10;
}

void spaceBfs(pair<int, int> now) {
    int x, y, nx, ny, cnt;
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    queue<pair<int, int>> q;

    cnt = 1;
    q.push(now);
    visited[now.first][now.second] = true;
    areaNum[now.first][now.second] = num;
    while(!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();

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

            if(0 > nx || nx >= n || 0 > ny || ny >= m) {
                continue;
            }

            if(graph[nx][ny] == 0 && visited[nx][ny] == false) {
                cnt++;
                q.push({nx, ny});
                areaNum[nx][ny] = num;
                visited[nx][ny] = true;               
            }
        }
    }

    areaSize.push_back(cnt);
}

void solve() {
    num = 0;
    // 0인 곳에서 움직일 수 있는 경우의 수 계산
    for(int i = 0; i < space.size(); i++) {
        if(visited[space[i].first][space[i].second] == false) {
            spaceBfs(space[i]);
            num++;
        }
    }

    // 1인 곳에서 1을 없애고 진행할 때 경우의 수 계산하여 result 배열에 저장
    for(int i = 0; i < wall.size(); i++) {
        wallBfs(wall[i]);
    }

    // 출력
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << result[i][j];
        }
        cout << endl;
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/16946
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.