[백준 4963번 섬의 개수(DFS)/ C++]

 

www.acmicpc.net/problem/4963

4963번: 섬의 개수

훟 예전 같았으면 이문제를 bfs로 풀었겠지만...!

더이상 예전의 내가 아니양!🥳 

난 dfs로 문제를 풀어낼 수 이찌 응켘엨엥

 

이 문제는 영역 개수를 세는 다른 문제들과 크게 다를 것은 없었당

하지만 하나 꼽자면 가로, 세로 뿐만 아니라 대각선에 있는 "1"까지 동일한 영역으로 간주하였기 때문에 그 부분을 dx, dy에 포함시켜주는것 만 포함했다면 완뵥!✨

 

#include <iostream>
#include <vector>

using namespace std;
int map[51][51];
int vis[51][51];
int w = 1, h = 1;

int dx[] = { -1, 1, -1, 1, 0, 0, -1, 1 };
int dy[] = { -1, 1, 1, -1, 1, -1, 0, 0 };
void dfs(int x, int y)
{
    vis[x][y] = true;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= h || ny >= w)
            continue;
        if (!vis[nx][ny] && map[nx][ny])
            dfs(nx, ny);
    }
}
int main()
{

    while (true) {
        int cnt = 0;
        cin >> w >> h;
        if (!w && !h)
            break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                vis[i][j] = false;
                cin >> map[i][j];
            }
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (!vis[i][j] && map[i][j]) {
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << "\n";
    }

    return 0;
}