[BAEKJOON] 4963 섬의개수 (C++)

[문제]

간단한 BFS문제입니다.

[조건]

가로, 세로, 대각선으로 연결되어 있는 섬의 전체개수를 찾는것

맵을 벗어나지않게 움직이며, 같은색의 섬만 움직일 수 있도록 판별하는것.
[해결순서]

가로, 세로, 대각선에대해 움직일수 있는 방법을 파악하는 것이 가장 중요한문제 라고생각합니다.

섬의개수문제는 여러 BFS에서 응용되기때문에 잘 기억하고 있는것을 추천함니다.

각각의 모든섬에서 다른섬으로 갈수있는지 판별하고,

더이상갈수없다면 섬의개수를 하나씩 증가시켜주면됩니다.

[부분소스코드]

순서대로 ↑ ↓  ← → ↖ ↗  ↘ ↙ 상 하 좌 우 좌상 우상 우하 좌하

int xX[8] = { 0, 0, -1, 1, -1, 1, 1, -1 };
int yY[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };

맵 범위 파악하기

맵범위경우에는 자신만의 스타일로 변경하는걸 추천드림니다.

1. 맵범위 안에 해당하는경우 true리턴

bool range(int y, int x) return x>=0 && y>=0 && y<h && x<w && !check[y][x];

2. 맵범위 안에 해당하지 않는경우 true리턴

bool range(int y, int x) return x<0||y<0||y>h-1||x>w-1||check[y][x];

3. 맵범위 안에 해당하지 않는경우 false리턴, 해당하는경우 true리턴

bool range(int y, int x) {
    if (x<0 || y<0 || y>h - 1 || x>w - 1 || check[y][x])
        return false;
    else
        return true;
}

등 가능함니다.

[전체소스코드]

 

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

#define MAX 51
#define endl "\n"
int w, h;
bool check[MAX][MAX];
int island[MAX][MAX];

int xX[8] = { 0, 0, -1, 1, -1, 1, 1, -1 };
int yY[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
typedef struct data {
    int y;
    int x;
}Data;
bool range(int y, int x) {
    if (x<0 || y<0 || y>h - 1 || x>w - 1 || check[y][x])
        return false;
    else
        return true;
}
int solve() {
    int cnt = 0;
    memset(check, 0, sizeof check);

    queue <Data> q;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            if (island[i][j] && !check[i][j]) {
                check[i][j] = true;
                q.push({ i,j });
                cnt++;
                while (!q.empty()) {
                    Data out = q.front(); q.pop();
                    for (int k = 0; k < 8; k++) {
                        int ny = out.y + yY[k];
                        int nx = out.x + xX[k];
                        if (range(ny, nx) && island[ny][nx]) {
                            check[ny][nx] = true;
                            q.push({ ny, nx });
                        }
                    }
                }
            }
        }
    return cnt;
}


int main() {
#ifdef _CONSOLE
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    while (1) {
        cin >> w >> h;

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

        memset(island, 0, sizeof island);
        for (int i = 0; i < h; i++)
            for (int j = 0; j < w; j++)
                cin >> island[i][j];
        cout << solve() << endl;
    }
}