섬들은 'x'로, 물은 '.'로 표시된 지도가 주어진다.
섬은 가로,세로,대각선이 연결되있으면 같은 섬이고 물은 가로,세로만 연결할 수 있다.
어떤 섬 A가 포함하고 있는 가장 높이가 높은섬의 높이가 K라면 A의 높이는 K+1이다.
높이가 0인섬부터 가장높은 섬의 높이까지 차례대로 개수를 구하는 문제이다.
한달전쯤 시도했다가 실패한 문제였다.
예전에 BFS를 약 한달동안 판적이 있어서 자신있었는데
이 문제를 접하고나니 아직 갈길이 멀다고 생각이 든다.
우선 바깥쪽 섬에서 안쪽 섬으로 들어오는 형식으로 풀어야지만 풀 수 있다.
처음에는 지도의 윤곽에 존재하는 물에서 시작을 해야한다.
문제예시처럼 지도의 모든 윤곽이 섬에의해 둘러싸여있다면 물을 queue에 넣을 수 없다.
이러한 경우에는 따로 예외처리를 해주었다.
물을 queue에 넣고 BFS를 진행하다가 섬을 만나면 물의 근원지 섬(?)에서 만난 섬을 연결시켜 주었다.
이렇게 연결된 인접리스트가 구성되면 DFS로 원하는 답을 한번에 구했다.
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M;
char map[51][51];
int visit[51][51];
bool adjmat[2555][2555];
vector<int> adj[2555];
queue<int> isl, wat;
int cnt = 1;
int dy[] = { -1,0,0,1,1,1,-1,-1 };
int dx[] = { 0,1,-1,0,-1,1,1,-1 };
vector<int> pos[2555];
vector<int> curr;
bool chk[2555];
void island(int iy, int ix) {
visit[iy][ix] = cnt;
isl.push(iy*M + ix);
pos[cnt].push_back(iy*M + ix);
while (!isl.empty()) {
int y = isl.front() / M, x = isl.front() % M;
isl.pop();
for (int i = 0;i < 8;i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M || visit[ny][nx] != 0 || map[ny][nx] == '.') continue;
visit[ny][nx] = cnt;
isl.push(ny*M + nx);
pos[cnt].push_back(ny*M + nx);
}
}
}
void water(int iy, int ix, int here) {
if (visit[iy][ix] != 0) return;
visit[iy][ix] = -1;
wat.push(iy*M + ix);
while (!wat.empty()) {
int y = wat.front() / M, x = wat.front() % M;
wat.pop();
for (int i = 0;i < 4;i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (map[ny][nx] == '.' && visit[ny][nx] == 0) {
visit[ny][nx] = -1;
wat.push(ny*M + nx);
}
else if (map[ny][nx] == 'x') {
if (!adjmat[here][visit[ny][nx]]) {
adjmat[here][visit[ny][nx]] = true;
adj[here].push_back(visit[ny][nx]);
curr.push_back(visit[ny][nx]);
// printf("%d->%d\n", here, visit[ny][nx]);
}
}
}
}
}
void solve(int num) {
queue<int> q;
for (int n = 0;n < pos[num].size();n++) q.push(pos[num][n]);
while (!q.empty()) {
int y = q.front() / M, x = q.front() % M;
q.pop();
for (int i = 0;i < 4;i++) {
int ny = y + dy[i], nx = x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (map[ny][nx] == '.' && visit[ny][nx] == 0) {
visit[ny][nx] = num;
q.push(ny*M + nx);
}
else if (map[ny][nx] == 'x' && visit[ny][nx] != num) {
if (!adjmat[num][visit[ny][nx]]) {
adjmat[num][visit[ny][nx]] = true;
adj[num].push_back(visit[ny][nx]);
curr.push_back(visit[ny][nx]);
// printf("%d->%d\n", num, visit[ny][nx]);
}
}
}
}
}
//void print() {
// for (int n = 0;n < N;n++) {
// for (int m = 0;m < M;m++)
// printf("%2d ", visit[n][m]);
// printf("\n");
// }
//}
int ans[51];
int Max = 0;
int dfs(int here) {
int ret = 0;
for (int &next : adj[here]) {
ret = max(ret, dfs(next) + 1);
}
if (here != 0) {
ans[ret]++;
Max = max(Max, ret);
}
return ret;
}
int main() {
bool flag = true;
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) {
scanf("%s", &map[n]);
if (flag) {
for (int m = 0;m < M;m++) {
if (map[n][m] == 'x') flag = false;
}
}
}
if (flag) { printf("-1\n"); return 0; }
for (int n = 0;n < N;n++)for (int m = 0;m < M;m++) {
if (map[n][m] == 'x' && visit[n][m] == 0) {
island(n, m);
cnt++;
}
}
for (int m = 0;m < M;m++) {
if (visit[0][m] == 0 && map[0][m] == '.') {
water(0, m, 0);
}
if (visit[N - 1][m] == 0 && map[N - 1][m] == '.') {
water(N - 1, m, 0);
}
}
for (int n = 1;n < N - 1;n++) {
if (visit[n][0] == 0 && map[n][0] == '.') {
water(n, 0, 0);
}
if (visit[n][M - 1] == 0 && map[n][M - 1] == '.') {
water(n, M - 1, 0);
}
}
if (curr.empty()) curr.push_back(visit[0][0]), adj[0].push_back(visit[0][0]);
while (!curr.empty()) {
vector<int> tmp;
for (int &n : curr) {
tmp.push_back(n);
}
curr.clear();
for (int &n : tmp) {
solve(n);
}
}
dfs(0);
for (int n = 0;n <= Max;n++) {
printf("%d ", ans[n]);
}
return 0;
}
| cs |
