cote/Intermediate
백준 4963 섬의 개수
geminanolja
2025. 4. 8. 05:23
https://www.acmicpc.net/problem/4963
#include <iostream>
#include <vector>
using namespace std;
int w, h;
vector<vector<int>> map;
vector<vector<bool>> visited;
// 8방향 (상, 하, 좌, 우 + 대각선)
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
void DFS(int x, int y)
{
visited[y][x] = true;
for (int i = 0; i < 8; ++i)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < w && ny < h)
{
if (!visited[ny][nx] && map[ny][nx] == 1)
{
DFS(nx, ny);
}
}
}
}
int main()
{
while (true)
{
cin >> w >> h;
if (w == 0 && h == 0) break;
map = vector<vector<int>>(h, vector<int>(w));
visited = vector<vector<bool>>(h, vector<bool>(w, false));
for (int y = 0; y < h; ++y)
{
for (int x = 0; x < w; ++x)
{
cin >> map[y][x];
}
}
int islandCount = 0;
for (int y = 0; y < h; ++y)
{
for (int x = 0; x < w; ++x)
{
if (map[y][x] == 1 && !visited[y][x])
{
DFS(x, y);
++islandCount;
}
}
}
cout << islandCount << endl;
}
return 0;
}