백준 4963 - 섬의 개수 - DFS

문제

문제링크 : https://www.acmicpc.net/problem/4963

풀이전략

1. 계속 같은 유형의 문제만 나온다. 이번에는 대각선까지 체크해야한다. 따라서 이번에는 대각선까지 체크하는 dx, dy를 만들어야한다.
2. 이외에는 서로 인접한 부분만 찾으면된다. 시간또한 충분하다.

코드

#include<bits/stdc++.h>

using namespace std;

int w, h;
int a[52][52];
int cnt;
// 대각선과 상하좌우를 체크하게 해주는 배열이다. 
int dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

void DFS(int r, int c){

    for(int i=0; i<8; i++){
        int rr = r+dy[i];
        int cc=  c+dx[i];
        if(a[rr][cc] == 1){
            a[rr][cc] = 0;
            DFS(rr, cc);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);

    

    while(1){
        cin >> w >> h;
        if(w == 0 && h == 0) break;

        cnt = 0;
        memset(a, 0, sizeof(a));

        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                cin >> a[i][j];
            }
        }
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
            	/// 섬이 있기 시작하면 그때부터 DFS시작
                if(a[i][j] == 1){
                    cnt++;
                    // 지나온 섬은 0으로 바꿔주어 중복 제거
                    a[i][j] = 0;
                    DFS(i,j);
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

소감

충분히 해결할 수 있다.