(매일 BOJ) C++ 4963번 섬의 개수

이번 문제는 2963번 섬의 개수다.

문제 개요

• 문제: 백준 4963번 - 섬의 개수
• 지도에서 섬(1)을 탐색하여 총 몇 개의 섬이 존재하는지를 구하는 문제
• 섬은 가로, 세로, 대각선으로 연결된 모든 1들로 구성
• 입력: 여러 테스트 케이스가 주어짐
• 각 테스트 케이스마다 지도의 가로(h), 세로(w) 가 주어짐
• 이후 w행 h열의 지도 정보가 입력됨
• 1은 땅, 0은 바다
• 대각선 포함 8방향 인접이면 같은 섬으로 간주
• 입력의 끝은 0 0 (종료 조건)

접근법 (DFS)

1. 전체 지도를 순회하면서
2. 방문하지 않은 땅(1)을 만나면 DFS로 연결된 모든 땅을 방문 처리
3. DFS를 시작할 때마다 섬 개수(result)를 +1
4. 모든 좌표를 검사한 후 result 출력

작성코드

#include <bits/stdc++.h>
using namespace std;

void DFS(vector<vector<int>> &arr,vector<vector<bool>> &visited,int,int);
int way_x[8] = {0,0,1,-1,1,1,-1,-1};
int way_y[8] = {1,-1,0,0,1,-1,-1,1};
int w,h;

int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    
    while(1){
    cin >> h >> w;
    if (w == 0 && h == 0) break;
    vector<vector<int>> arr(w,vector<int>(h));
    vector<vector<bool>> visited(w,vector<bool>(h,false));

    for(int i = 0; i < w; i++){
        for(int j = 0; j < h; j++){
            int a;
            cin >> a;
            arr[i][j] = a;
        }
    }
    int result = 0;
    for(int i = 0; i < w; i++){
        for(int j = 0; j < h; j++){
            if(arr[i][j] == 1 && !visited[i][j]){
                DFS(arr,visited,i,j);
                result += 1;
            }

        }
    }
    
    cout << result << '\n';

    }
}

void DFS (vector<vector<int>> &arr,vector<vector<bool>> &visited,int x,int y){
    visited[x][y] = true;
    int next_x,next_y;

    for(int i = 0; i < 8; i++){
        next_x = way_x[i] + x;
        next_y = way_y[i] + y;

        if(next_x >= 0 && next_y >= 0 && next_x < w && next_y < h && visited[next_x][next_y] == false && arr[next_x][next_y] == 1){
            DFS(arr,visited,next_x,next_y);
        }
    }
}