[백준] 4963번 섬의 개수

문제

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

풀이과정

2차원 배열에서 섬을 1이라고 했을 때 상하좌우와 대각선 4가지 경우를 다 검사하는 dfs를 구현해서 풀이했다. 앞에서 풀어본 단지번호붙이기를 풀어서 그런지 응용해서 풀 수 있었다.

소스코드

#include <iostream>

using namespace std;

int map[51][51];
int visited[51][51];
int dx[8] = { 0,0,1,-1,-1,-1,1,1 };
int dy[8] = { 1,-1,0,0,-1,1,-1,1 };
int w, h;

void dfs(int x,int y)
{
    visited[y][x] = 1;
    for (int k = 0; k < 8; k++)
    {
        int nx = x + dx[k]; int ny = y + dy[k];
        if (nx >= 0 && nx < w && ny >= 0 && ny < h)
        {
            if(map[ny][nx] == 1 && visited[ny][nx] == 0)
                dfs(nx, ny);
        }
    }

}
int main()
{

    while(true)
    {
        cin >> w >> h;

        if (w == 0 && h == 0) break;

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

        }

        int cnt = 0;

        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (visited[i][j] == 0 && map[i][j] == 1)
                {
                    dfs(j, i);
                    cnt++;
                }

            }
        }

        cout << cnt << "\n";
    }


    return 0;
}