풀이
문제를 조금 정리해 보자.
- 모든 섬
v에 대해, 최외곽 바다로 나가기 위해 반드시 거쳐야 하는 어떤 섬u가 존재하는가?
섬들간의 어떤 관계에 대해서 묻고 있다. 관계는 항상 그래프로 나타낼 수 있다. 문제의 정의가 그래프스럽게 생겼으니, Flood-fill을 이용해 육지와 바다를 각각 노드로 묶어 그래프로 만들고 생각해보자.
그래프에서 최외곽 바다를 1번 노드로 두고 문제를 다시 생각해 보자.
- 모든 섬 노드
v에 대해,1에서v로 가기 위해 반드시 거쳐야 하는 섬 노드u가 존재하는가?
이 말인즉슨,
- 그래프
G에서, 일반적으로 섬 노드인u와v만 고려하자. 모든v에 대해,u != v인u를 제거했을 때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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이