백준 4963 섬의 개수(dfs)

카테고리 없음

by 장동균 2021. 1. 14. 22:11

www.acmicpc.net/problem/4963

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

#include <iostream>
#include <string.h>

using namespace std;
const int MAX = 50;

typedef struct
{
    int x, y;
} Dir;

Dir dirMove[8] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
bool visited[MAX][MAX];
int graph[MAX][MAX];
int w, h;
int cnt;

void dfs(int x, int y)
{
    visited[x][y] = true;
    for (int i = 0; i < 8; i++)
    {
        int nextX = x + dirMove[i].x;
        int nextY = y + dirMove[i].y;
        if (!visited[nextX][nextY] && graph[nextX][nextY])
        {
            if (0 <= nextX && nextX < h && 0 <= nextY && nextY < w)
            {
                dfs(nextX, nextY);
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while (1)
    {
        cin >> w >> h;
        if (w == 0 && h == 0)
            break;
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                cin >> graph[i][j];
            }
        }
        for (int i = 0; i < h; i++)
        {
            for (int j = 0; j < w; j++)
            {
                if (!visited[i][j] && graph[i][j])
                {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";
        cnt = 0;
        memset(graph, 0, sizeof(graph));
        memset(visited, 0, sizeof(visited));
    }
}

크게 어렵지 않은 문제였다. 오늘부터 다시 차근차근 풀어나가자.