[BAE/<JOON> 문제풀이] 16000. 섬 (미완)

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

16000번: 섬

간단한 탐색문제 인줄 알았는데 자꾸 메모리 초과가 뜬다..(심지어 제한이 768메가에 5초임..)

 

아마도 단순히 BFS탐색만 하는게 아니라 뭔가 추가적인 기법이 필요하거나 함정이 숨어있는 문제 같다.

 

차라리 문제 자체가 복잡하다면 생각해볼 수 있는 경우가 많아서 여러가지 시도라도 해보는데 이건 문제마저 단순하니까 어디를 손봐야할지 모르겠다. 

 

오늘은 시간이 많이 지나서 못풀겠다..

 

내일 마저 풀어봐야겠다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int mvx[5] = { 0, 1, 0, -1, 0 };
int mvy[5] = { 0, 0, 1, 0, -1 };

int n, m;
vector<vector<int > > arr;
vector < vector<int> > ch;
vector < vector<int> > vis;
int icount = 2;

struct island {
    int x, y;
};

void dfs(int x, int y) {    
    ch[x][y] = 1;
    arr[x][y] = icount;
    if (x + 1 <= n) {
if (ch[x + 1][y] != 1 && arr[x + 1][y] == 1) {
    dfs(x + 1, y);
}
    }

    if (x - 1 >= 1) {
        if (ch[x - 1][y] != 1 && arr[x - 1][y] == 1) {
            dfs(x - 1, y);
        }
    }

    if (y + 1 <= m) {
        if (ch[x][y + 1] != 1 && arr[x][y + 1] == 1) {
            dfs(x, y + 1);
        }
    }

    if (y - 1 >= 1) {
        if (ch[x][y - 1] != 1 && arr[x][y - 1] == 1) {
            dfs(x, y - 1);
        }
    }
    ch[x][y] = 0;
}

int main()
{
    cin >> n >> m;    
    arr.resize(n + 1);
    ch.resize(n + 1);
    vis.resize(n + 1);
    for (int i = 1; i <= n; i++) {        
        arr[i].resize(m + 1);
        ch[i].resize(m + 1);
        vis[i].resize(m + 1);
        for (int j = 1; j <= m; j++) {
            char imsi;
            cin >> imsi;
            if (imsi == '.') {
                arr[i][j] = 0;
            }
            if (imsi == '#') {
                arr[i][j] = 1;
            }
        }
    }

    vector<pair<int, int> > ilist;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (arr[i][j] == 1) {
                //dfs(i, j);
                queue<island> q;
                q.push({ i, j });
                while (!q.empty()) {
                    int x = q.front().x;
                    int y = q.front().y;
                    q.pop();
                    arr[x][y] = icount;
                    for (int k = 1; k <= 4; k++) {
                        int mx = x + mvx[k];
                        int my = y + mvy[k];
                        if (arr[mx][my] != 1) continue;
                        q.push({ mx, my });
                    }
                }
                ilist.push_back({ i, j });
                icount++;
            }
            for (int k = 1; k <= n; k++) {
                for (int l = 1; l <= m; l++) {
                    ch[k][l] = 0;
                }
            }
        }
    }

    for (auto ip : ilist) {
        int first_found_island = -1;
        int safe = 0;
        queue<island> q;
        q.push({ ip.first, ip.second });
        int ino = arr[ip.first][ip.second];
        while (!q.empty()) {
            int x = q.front().x;
            int y = q.front().y;
            vis[x][y] = 1;
            q.pop();
            for (int i = 1; i <= 4; i++) {
                int mx = x + mvx[i];
                int my = y + mvy[i];
                if (vis[mx][my] == 1) continue;
                if (arr[mx][my] == ino) continue;
                if (mx == 1 || mx == n || my == 1 || my == m) {
                    safe = 1; //지도의 외곽으로 나갈 수 있음 = 안전
                    break;
                }
                if (arr[mx][my] > 1) {//섬을 찾았을 경우
                    if (ch[mx][my] == 1) {//안전한 섬인 경우
                        if (arr[mx][my] != first_found_island && first_found_island > 1) { //새로 발견 한 섬인 경우
                            safe = 1;
                            break; //이미 다른 섬을 하나 찾은 상태면 탐색 종료
                        }
                        else {
                            first_found_island = arr[mx][my];
                            continue;
                        }
                    }
                    else continue;
                }                
                q.push({ mx, my });   
            }
            if (safe == 1) {               
                break;
            }
        }

        if (safe == 1) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (arr[i][j] == arr[ip.first][ip.second]) {
                        ch[i][j] = 1; // ch가 1이면 안전한 섬
                    }
                }
            }
        }
        else {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    if (arr[i][j] == arr[ip.first][ip.second]) {
                        ch[i][j] = -1;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (ch[i][j] == 1) {
                cout << "O";
            }
            else if (ch[i][j] == -1) {
                cout << "X";
            }
            else if (ch[i][j] == 0) {
                cout << ".";
            }
        }
        cout << endl;
    }
    return 0;
}