[백준 4963] 섬의 개수

0. 제목

• 백준 4963 섬의 개수
• BOJ 4963 섬의 개수
• C++ 4963 섬의 개수

---

1. 문제

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

---

2. 풀이

• 백준 2667 단지번호붙이기 문제와 비슷한 문제이다. 2667번은 상하좌우를 따지는 것이었다면 이 문제에서는 대각선까지 고려해야한다.
• dfs에서는 여덟 방향 모두 탐색을 하면서 좌표가 0보다 작아지거나 주어진 넓이나 높이보다 같거나 커지면 넘어가면서 탐색한다.
• 재귀적으로 코드를 작성했으므로 여덟방향 중 이어진 부분이 있으면 그 덩어리를 전부 탐색완료 할 것이다.
• main함수에서 탐색을 할 때 값이 1이면서 방문하지 않은 부분을 반복문 내에서 탐색한다. 한 덩어리를 탐색완료 할 때마다 덩어리개수를 1씩 증가시켜준다.
• 탐색을 모두 마치면 정답이 나온다.
• 주의할 점으로는 입력을 받을 때 height, width 순서로 입력을 받아야한다. 왜냐하면 arr[0][0], arr[0][1] 과 같이 좌표를 지정할 때 arr[height][width] 로 지정하기 때문이다.

---

3. 코드

#include <iostream>
#include <cstring>
using namespace std;
#define MAX 50
 
int arr[MAX][MAX];
bool visited[MAX][MAX];
 
int w, h;
int cnt = 0;
 
int dx[8] = {-1,0,1,-1,1,-1,0,1};
int dy[8] = {1,1,1,0,0,-1,-1,-1};
 
void dfs(int x, int y){
    visited[x][y] = true;
    for(int i = 0; i < 8; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || nx >= w || ny < 0 || ny >= h)
            continue;
        if(arr[nx][ny] == 1 && visited[nx][ny] == false)
            dfs(nx, ny);
    }
}
 
int main(int argc, const char * argv[]) {
    while(true){
        memset(arr, 0, sizeof(arr));
        memset(visited, false, sizeof(visited));
        cnt = 0;
        cin >> h >> w;//입력 받는 순서 주의할 것
        if(h == 0 && w == 0)
            break;
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++){
                cin >> arr[i][j];
            }
        }
        for(int i = 0; i < w; i++){
            for(int j = 0; j < h; j++){
                if(arr[i][j] == 1 && visited[i][j] == false){
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << '\n';
    }
 
    return 0;
}