[백준/C++] #16946 벽 부수고 이동하기 4 (Flood Fill / BFS)

문제

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

알고리즘

: Flood Fill / bfs

 

구상

처음에는 단순하게 bfs를 통해 얼마나 많은 칸으로 이동할 수 있는지 구하는 줄 알고, 엥 왜 골드 3이지? 하고 풀었는데, 배열 크기가 최대 1000*1000까지 커질 수 있기에 시간초과가 났다.. 그래서 긴 탐색 시간을 줄여야한다고 생각했다. 하지만, 각각의 벽에서 이동할 수 있는 칸의 개수를 알아내야 했기에 이땐 변함없이 이중 for문이 필요했다. 그래서 떠오른게, 이동할 수 있는 칸들은 뭉텅이로 존재하는데, 뭉텅이의 크기를 파악하면, 벽의 상하좌우에 위치한 뭉텅이들의 크기만 고려할 수 있지 않을까?였다. 즉, 어떤 칸과 연결된 영역을 찾는 알고리즘인 flood fill을 통해 전처리만 빡세게해주면, 탐색 시간이 확연히 줄어 시간복잡도가 줄 것이라 판단한 것이다. 

 

그리고, 아직 메모리 제한은 잘 가늠이 되지 않아서 2차원 배열을 여러개 만들어도 되나..? 고민했었는데, 2차원 배열 3개(입력 배열, 방문여부 판단 배열, 최종 이동할 수 있는 칸 저장하는 배열)를 만들고도 다행히 별 문제 없었다. 

 

시간복잡도와 공간복잡도를 통해 사용할 수 있는 알고리즘을 판단한 후 로직을 짜는 연습을 해야겠다..!

 

그리고 이렇게 조금 어려웠다 오래걸렸다 주저리주저리 썼지만.. 사실 플러드필 기초 개념에 뭉텅이 크기 계산만 조금 추가되었을 뿐 그리 어려운 문제는 아니었던 것 같다. 

 

코드 + 풀이

BFS를 이용하여 0의 뭉텅이를 라벨링하고, 각 뭉텅이의 크기를 기록한다. 

기록할때 큐를 사용하는데, 라벨링 인덱스 번호에 맞게 크기값이 push되기에 어떤 뭉텅이의 크기인지 식별 가능하다. 

 
벽 부수면 이동할 수 있는 상하좌우에 존재하는 뭉텅이들을 라벨로(cid) 확인하고, 해당 뭉텅이들의 크기 더하자.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#define MAX 1010
using namespace std;
/*
16946 벽 부수고 이동하기4
0: 이동 가능, 1: 이동 불가한 벽

각각의 벽에 대해, 벽을 부수고 이동할 수 있는 칸의 개수를 구한다.
- 벽을 부수면 이동할 수 있는 칸의 개수를 10으로 나눈 나머지 출력
*/

int N, M;
vector<vector<int>> map(MAX, vector<int>(MAX)); // 맵 저장
vector<vector<int>> visit(MAX, vector<int>(MAX, 0)); // 방문 및 라벨링 정보
vector<int> componentSize; // 각 라벨별 크기 저장
vector<pair<int, int>> dxy = { {0, 1}, {-1, 0}, {0, -1}, {1, 0} }; // 방향벡터

// BFS로 특정 0의 뭉텅이를 라벨링하고 크기 측정
void bfs(int x, int y, int compId) {
    queue<pair<int, int>> q;
    q.push({ x, y });
    visit[y][x] = compId; // 라벨링
    int cnt = 1; // 해당 뭉텅이의 크기

    while (!q.empty()) {
        auto now = q.front();
        q.pop();

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

            if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
            if (map[ny][nx] != 0 || visit[ny][nx] != 0) continue;

            visit[ny][nx] = compId; // 컴포넌트 id를 visit 배열에 넣어둠
            cnt++;
            q.push({ nx, ny });
        }
    }

    componentSize.push_back(cnt); // 뭉텅이 크기 넣어둠. id 작은 순대로 들어갈 것
}

void solution() {
    int compId = 1; // 라벨링용 아이디

    // 모든 0의 뭉텅이를 라벨링
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0 && visit[i][j] == 0) {
                bfs(j, i, compId++); 
            }
        }
    }

    // 벽을 부수고 이동 가능한 칸 계산
    vector<vector<int>> ans(N, vector<int>(M, 0)); // 정답 기입하는 배열

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 1) {
                int moveCount = 1; // 자기 자신 포함
                set<int> uniqueComponents; // 아래서 중복으로 같은 뭉텅이 크기 더하지 않기 위하여 set 사용

                // 얼마나 이동할 수 있는지 작성

                for (int k = 0; k < 4; k++) {
                    int nx = j + dxy[k].first;
                    int ny = i + dxy[k].second;

                    if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
                    if (map[ny][nx] == 0) {
                        int cid = visit[ny][nx]; 
                        uniqueComponents.insert(cid);
                    }
                }

                for (auto cid : uniqueComponents) {
                    moveCount += componentSize[cid - 1]; // cid에 맞는 크기 더하기. -1해서 인덱스로 맞추기.
                }

                ans[i][j] = moveCount % 10;
            }
        }
    }

    // 출력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0) {
                cout << 0;
            }
            else {
                cout << ans[i][j];
            }
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> N >> M;
    map.resize(N, vector<int>(M));
    visit.resize(N, vector<int>(M, 0));

    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < M; j++) {
            map[i][j] = str[j] - '0';
        }
    }

    // 로직
    solution();

    return 0;
}