[백준/C++] 4963번_섬의 개수🏝

문제는 다음과 같습니다.

전형적인 dfs문제이구요,
앞서서 풀었었던 문제에서 아주 조금 응용?된 문제라 보면 됩니다.

앞서서는, 상하좌우에 대해서만 관계가 성립했는데
📌이번문제는 대각선까지 섬의 범위가 포함됩니다.📌

그래서 dfs함수 내에도 대각선에 대해서도 dfs를 수행하도록 하였습니다.

문제가 간단하므로, 간단하게 짚고 넘어가겠습니다.

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

int a[52][52]={0, };
int ch[52][52]={0, };
vector<int> res;
int tmp;

void DFS(int u, int v){
  ch[u][v]=1;

  // 상,하,좌,우,대각선에 대해서 dfs수행
  if(ch[u][v-1]==0 && a[u][v-1]==1) DFS(u, v-1);
  if(ch[u][v+1]==0 && a[u][v+1]==1) DFS(u, v+1);
  if(ch[u-1][v]==0 && a[u-1][v]==1) DFS(u-1, v);
  if(ch[u+1][v]==0 && a[u+1][v]==1) DFS(u+1, v);

  if(ch[u+1][v+1]==0 && a[u+1][v+1]==1) DFS(u+1, v+1);
  if(ch[u+1][v-1]==0 && a[u+1][v-1]==1) DFS(u+1, v-1);
  if(ch[u-1][v+1]==0 && a[u-1][v+1]==1) DFS(u-1, v+1);
  if(ch[u-1][v-1]==0 && a[u-1][v-1]==1) DFS(u-1, v-1);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while(1){
      int w, h; cin>>h>>w;
      if(w==0 && h==0) break;
      
      for(int i=1; i<=w; i++){
        for(int j=1; j<=h; j++){
          int tmp; cin>>tmp;
          a[i][j]=tmp;
        }
      } // 2차원 배열 입력받기 끝

      int tmp=0;
      for(int i=1; i<=w; i++){
        for(int j=1; j<=h; j++){
          if(ch[i][j]==0 && a[i][j]==1){
            DFS(i, j);
            tmp++; // 섬의 개수 count하기
          }
        }
      }
      cout<<tmp<<"\n"; // 섬의 개수 출력

      for(int i=1; i<=w; i++){
        for(int j=1; j<=h; j++){
          ch[i][j]=0;
          a[i][j]=0;
        }
      } // a배열, ch배열 초기화

    } // while문 끝
    return 0;
}