섬들은 '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 |
저게 bfs가 어려워 질 수 있는 예겠네요.. ㄷ
답글삭제난도가 쉽지 않아 보이긴 하던데요.. 딱 봐도 bfs 느낌이 나는데 정작 구현하기는..
그런데 이런 문제들도 간혹 있더라고요.
bfs는 숨겨놓고.. 수학으로 접근해 보시지!!
떡하니 알고리즘 분류에는 수학이라고 되어 있는데.. 이런 경우는 정말.. ㅠㅠ
맨날 거울설치 노래를 부르면서
삭제정작 거울설치는 안 풀고 다른 수학문제만 풀고 있네요.. ㅋㅋㅋ
다른 분들 (예를 들어서 어느 분이 갓자손님이라고 부르시는 분이라던지..)과 비교해 봐도
수학 문제를 상당히 많이 풀었지.. 그 분들이 경험해 본
다른 알고리즘은 많이 안 하긴 했네요..
전 수학문제를 잘 접근 못하겠더라구요 ㅠㅠ
삭제정말 이 문제는 구현적인 측면에서 힘들었네요