4963번: 섬의 개수

[yeonddori]

문제: https://www.acmicpc.net/problem/4963

문제 설명

2차원 배열로 주어진 지도에서 섬의 개수를 구하는 문제입니다.
지도는 가로와 세로 길이가 각각 w와 h로 주어지며, 1은 땅, 0은 바다를 나타냅니다.
8방향(상하좌우 + 대각선)으로 연결된 땅은 하나의 섬으로 간주됩니다.
지도를 탐색하여 섬의 개수를 세어야 하며, 입력의 끝은 0 0으로 주어집니다.

문제 풀이

탐색을 위해 BFS를 사용하였고, 방문한 노드를 기록하여 중복 탐색을 방지합니다.
지도에서 땅을 발견하면 해당 섬을 모두 탐색하고 섬의 개수를 증가시키며, 최종적으로 섬의 개수를 출력합니다.

코드

#include <bits/stdc++.h>
using namespace std;

int dx[8] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[8] = {1, -1, 0, 1, -1, 0, 1, -1};

void bfs(vector<vector<int>>& maps, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < maps.size() && ny >= 0 && ny < maps[0].size()
                && maps[nx][ny] == 1 && !visited[nx][ny]) {
                q.push({nx, ny});
                visited[nx][ny] = true;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (true) {
        int w, h;
        cin >> w >> h;
        if (w == 0 && h == 0) break;

        vector<vector<int>> maps(h, vector<int>(w));
        vector<vector<bool>> visited(h, vector<bool>(w));
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> maps[i][j];
            }
        }

        int cnt = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (maps[i][j] == 1 && !visited[i][j]) {
                    bfs(maps, visited, i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }

    return 0;
}

후기

저번에 풀었던 1926번: 그림 문제와 매우 비슷해서 조금 쉽게 푼 것 같습니다. 그리고 대각선을 포함하여 8방향 탐색하는 문제는 처음 접해봐서 신기했어요!