백준, BOJ, 16946번, 벽 부수고 이동하기 4 : C++ [CPP]

 

1000* 1000의 탐색은

쉽게 시간초과가 된다는 것을 충분히 인지해야 한다.

그래서 어려웠다.

1000* 1000 사이즈의 노드에서 하나씩 BFS하는 것은

(1000 * 1000) 에 대해 (1000*1000) 을 수행하는 것과 같다.

즉, 시간초과다.

 

 

 

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

 

 

---

 

#맞는 풀이

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>

#define X first
#define Y second
#define SIZE 1000

using namespace std;

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int r, c; //행, 열

char given[SIZE][SIZE];
int visited[SIZE][SIZE];

vector <pair<int, int>> vec;

int made[SIZE][SIZE];

//0인 영역에 대해서 해당 영역 크기를 영역안의 모든 노드가 저장하게 만듦
//벽에 대해 4방향의 노드만 합치면 됨.
//하지만 영역이 겹치면 안된다. 


vector<int> area; //영역의 넓이를 저장할 컨테이너
int area_num = 0; // 0번 영역부터 시작.


//BFS로 돌려서 갈 수 있는 모든 칸 수 반환.
int BFS(int x, int y) {
    queue<pair<int, int>> q;
    q.push({ x,y });
    visited[x][y] = 1;
    vec.push_back({ x,y });
    int cnt = 0; //해당 벽을 부순뒤 갈 수 있는 칸 수
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        made[cur.X][cur.Y] = area_num; // 해당 노드에서 BFS 했을 때 무슨 영역에 속하는지
        cnt++; // 큐에서 꺼낼때마다 추가.
        for (int dir = 0; dir < 4; dir++) {
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            //범위
            if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
            //벽으로 막혀있거나 방문했으면 
            if (visited[nx][ny] != 0 || given[nx][ny] == '1')continue;
            q.push({ nx,ny });
            vec.push_back({ nx,ny });
            visited[nx][ny] = 1;

        }
    }
    return cnt;
}


int main() {
    cin >> r >> c;

    //입력받기
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            given[i][j] = s[j];
            made[i][j] = -1; // made는 -1로 초기화.
        }
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            //0인 영역 확인
            if (given[i][j] == '0' && visited[i][j] == 0) {
                
                int val = BFS(i, j); //돌려보고
                area.push_back(val); // 해당영역의 크기 vector에 넣음
                area_num++; //다음 영역을 찾으러감.

            }
        }
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            //부술 벽 정함
            if (given[i][j] == '1') {
                int x = 1; // 자기자신 포함해야함

                // 몇 번 영역과 맞닿아있는지 확인. (중복x)
                set <int> s;

                //4방향의 값중 given이 0인 부분만
                for (int dir = 0; dir < 4; dir++) {
                    int nx = i + dx[dir];
                    int ny = j + dy[dir];

                    //범위
                    if (nx < 0 || nx >= r || ny < 0 || ny >= c)continue;
                    if (given[nx][ny] == '1')continue; //벽이 있는 노드는 조사하지 않음.
                    s.insert(made[nx][ny]); //해당 영역 번호를 집어넣음

                }

                for (int k : s) {
                    x += area[k]; //k 영역의 넓이 더해줌
                }
                x %= 10; //10으로 나눈 나머지
                cout << x;

            }
            else {
                cout << 0;
            }
            
        }
        cout << "\n";
    }

    return 0;
}

 

 

1. 0을 따로 조사해서 영역의 넓이와 영역 번호를 설정

2. 1을 조사하면서 4방향에 0이 있는지 조사

2-1. 0을 조사하면서 해당 영역을 집어넣음

(영역을 넣는 Container를 Set으로 설정하여 중복된 영역이 들어가지 않도록)

-> 예를 들어 아래 0과 오른쪽 0이 사실 같은 영역이면 2번 세면 안된다는 말.

2-2 해당 영역에 대한 넓이를 추가

3. 출력