백준 16946번 벽 부수고 이동하기4

백준 16946번 벽 부수고 이동하기4

#include <iostream>
#include <string>
#include<cstring>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int n, m;
int wall[1001][1001];
pair<int,int> ret[1001][1001];
int visited[1001][1001];
int ans[1001][1001];
int Count = 1;
 
//영역의 번호 
int cntgd = 1;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
 
queue<pair <int, int> > Rmb;
void DFS(int y, int x) {
    //이동했던 장소 기억
    visited[y][x] = true;
    Rmb.push(make_pair(y, x));
    for (int i = 0; i < 4; i++) {
        int nexty = y + dy[i];
        int nextx = x + dx[i];
        //움직일수 있는 다음 이동장소 범위 만족하고, 방문하지않았으며 
        //벽이없어서 이동할 수 있는 곳 발견하면 재귀 실행
        if (0 <= nexty && nexty < n && 0 <= nextx && nextx < m) {
            if (!visited[nexty][nextx] && !wall[nexty][nextx]) {
                Count++;
                DFS(nexty, nextx);
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    vector<string> strwall(n);
    for (int i = 0; i < n; i++)
        cin >> strwall[i];
    //입력받은 문자열 int형으로 변환
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            wall[i][j] = strwall[i][j] - '0';
        }
 
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //벽이 있는 경우 벽을 허물고 이동할 수 있는 개수 카운트
            if (wall[i][j] == 0) {
                Count = 1;
                DFS(i, j);
                //영역들이 이동할수있는 영역의 넓이를 ret[i][j].first에 저장해주고 
                //ret[i][j].second에는 영역의 번호를 지정해준다.
                while (!Rmb.empty()) {
                    if (ret[Rmb.front().first][Rmb.front().second].first < Count) {
                        ret[Rmb.front().first][Rmb.front().second] = make_pair(Count,cntgd);
                    }
                    Rmb.pop();
                }
                cntgd++;
            }
        }
    }
    
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //벽이 있는 경우 벽을 허물고 이동할 수 있는 개수 카운트
            if (wall[i][j] != 0) {
                //들린 영역번호 저장하는 벡터 선언
                vector<int> ground;
                //자기 자신을 0으로바꿧을때 움직일수 있는 영역넓이 1부터 시작
                int val = 1;
                for (int k = 0; k < 4; k++) {
                    int nexty = i + dy[k];
                    int nextx = j + dx[k];
                    //이동가능한 범위에있는지 체크
                    //이동한 영역이 이미 들렸던 곳인지 영영번호로 확인하고
                    //들리지않았다면 영역의 넓이를 더해준다. 
                    //그리고 들린 영역의 번호를 들렸다고 표시해줌.
                    if (0 <= nexty && nexty < n && 0 <= nextx && nextx < m) {
                        int a = ret[nexty][nextx].second;
                        bool Check = true;
                        for (int b = 0; b < ground.size(); b++) {
                            //동서남북방향으로 들린 영역의 번호를 저장한 벡터에서
                            //같은 영역번호가 존재하면? 또 더해줄필요가 없다.
                            if (ground[b] == a)
                                Check = false;
                        }
                        if (Check) {
                            val += ret[nexty][nextx].first;
                            ground.push_back(a);
                        }
                    }
                }
                //동서남북 영역 중복되지않게 넓이 모두 더해준 값 ans[i][j]에저장.
                ans[i][j] = val;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << ans[i][j]%10;
        }
        cout << "\n";
    }
    
    return 0;
}

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

시간복잡도때문에 애를 먹은 문제입니다.문제를 푸는 방법은

1.주어진 지도의 각 영역넓이를 구해놓는다.

2.벽을 없애고 현위치에서 동서남북방향으로 중복되지않게 구해놓은 영역의 넓이를 더해준다.

였습니다. 밑의 코드는 다른 방식으로 풀었지만 시간복잡도때문에 시간초과가 떴습니다. 

#include <iostream>
#include <string>
#include<cstring>
#include<queue>
#include <vector>
#include <algorithm>
#include<cmath>
using namespace std;
 
int n, m;
int wall[1001][1001];
int ret[1001][1001];
int visited[1001][1001];
int Count=1;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
void DFS(int y, int x) {
    //이동했던 장소 기억
    visited[y][x] = true;
    for (int i = 0; i < 4; i++) {
        int nexty = y + dy[i];
        int nextx = x + dx[i];
        //움직일수 있는 다음 이동장소 범위 만족하고, 방문하지않았으며 
        //벽이없어서 이동할 수 있는 곳 발견하면 재귀 실행
        if (0 <= nexty && nexty < n && 0 <= nextx && nextx < m) {
            if (!visited[nexty][nextx]&&!wall[nexty][nextx]) {
                Count++;
                DFS(nexty, nextx);
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    vector<string> strwall(n);
    for (int i = 0; i < n; i++)
        cin >> strwall[i];
    //입력받은 문자열 int형으로 변환
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            wall[i][j] = strwall[i][j] - '0';
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            //벽이 있는 경우 벽을 허물고 이동할 수 있는 개수 카운트
            if (wall[i][j] != 0) {
                //DFS실행 할 때마다 다시 visited 초기화
                memset(visited, 0, sizeof(visited));
                //본인 위치 1개 부터 시작
                Count = 1;
                //벽 허물기
                wall[i][j] = 0;
                DFS(i, j);
                //이동가능한 수 저장
                ret[i][j] = Count;
                //계산 끝나고 다시 벽 세우기
                wall[i][j] = 1;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << ret[i][j];
        }
        cout << "\n";
    }
    return 0;
}