[백준][C++] 4964: 섬의 개수

문제

4963번: 섬의 개수

풀이

그래프 탐색, 너비 우선 탐색

 

간단한 너비 우선 탐색 문제로, 8방향만 주의하면 된다.

지도의 (0, 0)부터 탐색을 시도하며, 현재 타일이 방문하지 않은 섬이라면 해당 타일부터 너비 우선 탐색을 실시한다. 상하좌우 대각 8방향에서 방문하지 않은 섬이 있다면 방문하고 이를 반복한다. 탐색이 종료되면 시작한 타일이 포함된 섬을 하나 방문한 것으로 섬의 개수가 1 증가한다. 

코드

#include <iostream>
#include <queue>

using namespace std;

int w, h;
int m[50][50];
bool visited[50][50];
int move_x[8] = { 0, 0, 1, -1, -1, -1, 1, 1 };
int move_y[8] = { 1, -1, 0, 0, -1, 1, -1, 1 };

int numIslands()
{
    memset(visited, false, sizeof(visited));
    int result = 0;

    // w, h 주의
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            if (m[i][j] == 1 && visited[i][j] == false)
            {
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                visited[i][j] = true;

                while (!q.empty())
                {
                    int current_x = q.front().first;
                    int current_y = q.front().second;
                    q.pop();

                    // 상하좌우, 대각 8방향, 너비 우선 탐색
                    for (int k = 0; k < 8; ++k)
                    {
                        int next_x = current_x + move_x[k];
                        int next_y = current_y + move_y[k];

                        if (next_x < 0 || next_x >= h || next_y < 0 || next_y >= w 
                            || visited[next_x][next_y] == true || m[next_x][next_y] == 0)
                        {
                            continue;
                        }

                        q.push(make_pair(next_x, next_y));
                        visited[next_x][next_y] = true;
                    }
                }

                result++;
            }
        }
    }

    return result;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    // w, h 주의
    while (cin >> w >> h)
    {
        if (w == 0 && h == 0)
        {
            break;
        }

        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                cin >> m[i][j];
            }
        }

        cout << numIslands() << '\n';
    }

    return 0;
}