섬의 개수 (feat. 백준, 4963번)

섬의 개수
https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
int W, H, dx[8], dy[8], arr[51][51];
bool visit[51][51];
int bfs(){
    register int ans = 0;
    memset(visit, false, sizeof(visit));
    for(register int w = 1, h; w <= W; ++w)
        for(h = 1; h <= H; ++h)
            if(!visit[h][w] && arr[h][w]){
                ++ans;
                queue<pair<int, int>> q;
                q.push(make_pair(h, w));
                visit[h][w] = true;
                while(!q.empty()){
                    auto p = q.front(); q.pop();
                    register int x = p.first, y = p.second;
                    for(register int d = 0, nx, ny; d < 8; ++d){
                        nx = x + dx[d], ny = y + dy[d];
                        if(1 <= nx && nx <= H && 1 <= ny && ny <= W && !visit[nx][ny] && arr[nx][ny])
                            visit[nx][ny] = true, q.push(make_pair(nx, ny));
                    }
                }
            }
    return ans;
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    dx[7] = dx[0] = dx[1] = -1, dx[2] = dx[6] = 0, dx[3] = dx[4] = dx[5] = 1;
    dy[0] = dy[4] = 0, dy[1] = dy[2] = dy[3] = 1, dy[5] = dy[6] = dy[7] = -1;
    while(1){
        cin >> W >> H;
        if(W == 0 && H == 0)
            break;
        for(register int h = 1, w; h <= H; ++h)
            for(w = 1; w <= W; ++w)
                cin >> arr[h][w];
        cout << bfs() << "\n";
    }
    return 0;
}
// *&)*@*

 

1. 전형적인 bfs 문제입니다.
2. 대각선에 대한 고려가 이루어져야 합니다.
3. 결국 전체 영역중에 이어지는 땅의 개수가 총 몇개인가 하는 문제입니다. 이때 이어지는 땅은 1개 이상인 경우입니다.