16000 : 섬

풀이

문제를 조금 정리해 보자.

  • 모든 섬 v에 대해, 최외곽 바다로 나가기 위해 반드시 거쳐야 하는 어떤 섬 u가 존재하는가?

섬들간의 어떤 관계에 대해서 묻고 있다. 관계는 항상 그래프로 나타낼 수 있다. 문제의 정의가 그래프스럽게 생겼으니, Flood-fill을 이용해 육지와 바다를 각각 노드로 묶어 그래프로 만들고 생각해보자.

그래프에서 최외곽 바다를 1번 노드로 두고 문제를 다시 생각해 보자.

  • 모든 섬 노드 v에 대해, 1에서 v로 가기 위해 반드시 거쳐야 하는 섬 노드 u가 존재하는가?

이 말인즉슨,

  • 그래프 G에서, 일반적으로 섬 노드인 uv만 고려하자. 모든 v에 대해, u != vu를 제거했을 때 1에서 v로의 경로가 존재하지 않게 되는 u가 존재하는가?

그래프 상에서 어떤 정점을 제거했을 때 경로가 단절 된다는 것은 그래프의 컴포넌트가 둘 이상으로 분리 된다는 것이다. 이는 절점의 개념과 유사하다. 절점인 u를 제거했을 때 경로가 단절되는 노드들을 (단절되는 노드들만!!!) 찾아 주어야 한다.

단순히 절점을 찾는, 혹은 절점을 만나면 체킹하는 naive한 아이디어로는 문제를 풀 수 없다. 위와 같은 방법으로는, 단절점에 의해 단절되는 노드와 단절되지 않는 노드를 구분할 수 없기 때문이다.

이는 절점을 구하는 알고리즘을 응용하여 구현할 수 있다.

그래프 G에서 1번 노드부터 dfs를 돌리면서 dfs tree를 만들어 나가자. 이 과정에서 u가 절점인지 판별해야 한다. dfs를 돌리고 있기 때문에, 어떤 u가 절점인 섬으로 밝혀지는 순간에, 방금 들어갔다 나온 u의 sub-tree에 속한 모든 노드들은 G에서 분리되는 것이 자명하다.

dfs ordering을 하기 때문에 sub-tree의 노드들은 연속된 index를 가진다. 절점을 구하는 과정에서 지나는 노드들을 기억해 두면 O(V+E) 즈음에 이를 구할 수 있다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int dx[] = { 0,0,-1,1 }, dy[] = { -1,1,0,0 };
const int n_ = 2000+2, nm_ = 4000000+1;

char a[n_][n_];
int n, m, cnt, num, vst[n_][n_], chk[nm_], con[nm_], isSum[nm_];
vector<int> stk, gph[nm_];

void go(int x, int y, int num) {
    vst[x][y] = num;
    for (int i = 0; i < 4; i++) {
        int nx = x+dx[i], ny = y+dy[i];
        if (a[x][y] == a[nx][ny] && !vst[nx][ny]) {
            go(nx, ny, num);
        }
        else if (a[x][y] != a[nx][ny] && vst[nx][ny]) {
            if (con[vst[nx][ny]] == num) continue;
            gph[num].push_back(vst[nx][ny]);
            gph[vst[nx][ny]].push_back(num);
            con[num] = num;
            con[vst[nx][ny]] = num;
        }
    }
}

void buildGraph() {
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        if (!vst[i][j]) go(i, j, ++num);
}

void init() {
    fill(con, con+num+1, 0);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        if (a[i][j] == '#') isSum[vst[i][j]] = 1;
}

void gogo(int now) {
    int mn = num;
    chk[now] = ++cnt;
    stk.push_back(now);
    for (int nxt : gph[now]) {
        if (!chk[nxt]) {
            gogo(nxt);
            if (isSum[now] && chk[nxt] == chk[now]) {
                while (!stk.empty() && stk.back() != now) {
                    con[stk.back()] = 1;
                    stk.pop_back();
                }
            }
            stk.push_back(now);
        }
        mn = min(mn, chk[nxt]);
    }
    chk[now] = mn;
    return;
}

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", a[i]+1);
    stk.reserve(nm_);
}

void process() {
    buildGraph();
    init();
    gogo(1);
}

void output() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '.') {
                printf(".");
                continue;
            }
            int num = vst[i][j];
            printf("%c", con[num] && chk[num] != 1 ? 'X' : 'O');
        }
        puts("");
    }
}

int main() {
    input();
    process();
    output();
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-11-23 10:12

Read more posts by this author