백준 16946번: 벽 부수고 이동하기 4 (C++)

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

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

---

Solved By: Flood-Fill

 

저번 포스팅과 이어지는 문제입니다. Flood-Fill이 무엇인지 배웠다면 이것을 사용하여 시간문제를 해결할 수도 있습니다. 1인 칸에서 0의 개수를 세는 BFS는 다른 1인 칸에서도 개수를 셀 수 있기 때문에 꽤 오래 걸립니다.

 

하지만, 4가지 방향을 확인했을 때, 어떤 0이 어떤 영역에 속하는지 알고, 그 영역의 크기를 안다면 각 1칸당 O(4)로 시간을 단축시킬 수 있습니다.

 

외람된 말이지만 result 2차원 배열을 선언하여 답을 구하는 방법은 틀리고, 입력받은 배열을 그대로 사용하는 코드가 맞았는데 메모리 문제인지 틀린 답을 도출하는지는 아직 파악이 안 됩니다..

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define MAX 1001
using namespace std;

int n, m;
int graph[MAX][MAX];
bool visited[MAX][MAX];

// flood fill 관련 선언 data structure
int zeroAreaNum[MAX][MAX]; // 각 Coor가 어느 영역에 속하는지 번호로 나타냄
int zeroAreaCnt = 0; // 그 번호가 이 변수임
vector<int> zeroArea; // 해당 영역의 영역 크기 값
//

struct Point{
    int y, x;
};

Point dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// flood-fill
void bfs(int row, int col){
    queue<Point> q;
    q.push({row, col});
    visited[row][col] = true;
    zeroAreaNum[row][col] = zeroAreaCnt;
    
    int area = 1;
    
    while(!q.empty()){
        int ny = q.front().y;
        int nx = q.front().x;
        
        q.pop();
        
        for(int i = 0; i < 4; i++){
            int dy = ny + dir[i].y;
            int dx = nx + dir[i].x;
            
            if(dy <= n && dy >= 1 && dx <= m && dx >= 1){
                if(!visited[dy][dx] && graph[dy][dx] == 0){
                    area++;
                    visited[dy][dx] = 1;
                    q.push({dy, dx});
                    zeroAreaNum[dy][dx] = zeroAreaCnt;
                }
            }
        }
    }
    
    zeroArea.push_back(area);
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        string s; cin >> s;
        for(int j = 0; j < m; j++){
            graph[i][j + 1] = s[j] - '0';
        }
    }
    
    // 각 좌표의 영역 번호 init
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            zeroAreaNum[i][j] = -1;
        }
    }
    
    // 0끼리 붙어있는 위치들을 flood-fill로 영역화 시킨다.
    // 영역들의 번호를 매기고, 그 영역 번호의 해당하는 크기 값을 리턴하도록 한다.
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(!visited[i][j] && graph[i][j] == 0){
                bfs(i, j);
                zeroAreaCnt++;
            }
        }
    }
    
    // 왜 result라는 새로운 2차원 배열을 선언한 후에
    // graph[i][j] == 1이면 result[i][j]에서 4가지 방향 탐색 후, +1하면
    // 답이라고 하지 않는걸까
    // 메모리 초과라고 하기엔 '틀렸습니다'가 나오기 때문에
    // 틀린 답을 도출한다는 소리인데..
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(graph[i][j] == 1){
                set<int> st;
                for(int k = 0; k < 4; k++){
                    int dy = i + dir[k].y;
                    int dx = j + dir[k].x;
                    if(dy >= 1 && dy <= n && dx >= 1 && dx <= m){
                        if(zeroAreaNum[dy][dx] == -1) continue;
                        
                        int getAreaNum = zeroAreaNum[dy][dx];
                        if(st.count(getAreaNum) == 0){
                            st.insert(getAreaNum);
                            graph[i][j] += zeroArea[getAreaNum];
                        }
                    }
                }
                
                graph[i][j] %= 10;
            }
        }
    }
    
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout << graph[i][j];
        }
        cout << '\n';
    }
    
    return 0;
}