[BOJ 4963] 섬의 개수 C++

섬의 개수

난이도: Silver 2
번호: 4963
사용 함수, 자료 구조: memset
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

4963번: 섬의 개수

C++

• 상하좌우와 대각선 방향까지 8방 탐색을 할 수 있도록 방향배열(dX, dY)을 설정해준다.

    const int dX[] = {1, -1, 0, 0, 1, 1, -1, -1};
    const int dY[] = {0, 0, -1, 1, 1, -1, 1, -1};

• 8방 탐색중에 Out of Bound가 발생할수 있는데 해결에는 2가지 방법이 있다.

  1. if 조건 추가

      if (i < 0 || j < 0 || i >= M || j >= N)
          continue; 

  2. 그래프 배열 상하좌우에 1칸씩 여유공간을 만들어준다.

     • 이 문제에서는 1 ≤ W, H ≤ 50이란 조건이 있으므로 노드를 담는 배열에 0 ~ 51 인덱스까지 공간을 할당해주면 탐색중 1~50 테두리 밖(0, 51)으로 나가더라도 에러가 발생하지 않는다.

#include <iostream>
#include <cstring>
using namespace std;

const int dX[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dY[] = {0, 0, -1, 1, 1, -1, 1, -1};
bool node[52][52];
int cnt;

void reset()
{
    cnt = 0;
    memset(node, 0, sizeof(node));
}

void DFS(int i, int j)
{
    node[i][j] = false;

    for (int k = 0; k < 8; k++)
    {
        int x = j + dX[k];
        int y = i + dY[k];
        if (node[y][x])
            DFS(y, x);
    }
}

int main(void)
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);

    while (1)
    {
        int W, H;
        cin >> W >> H;

        if (W + H == 0)
            return (0);

        reset();

        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
            {
                int n;
                cin >> n;
                if (n == 1)
                    node[i + 1][j + 1] = true;
            }

        for (int i = 1; i <= H; i++)
            for (int j = 1; j <= W; j++)
            {
                if (node[i][j] == true)
                {
                    cnt++;
                    DFS(i, j);
                }
            }
        cout << cnt << '\n';
    }
}