백준 | 4963. 섬의 개수

1. idea - 1 만나면 DFS실행해서 연결된 1을 하나의 단지로 묶기

• 이차원 배열을 순회하면서 아직 방문 안 한 1을 찾음 → 새로운 섬 시작
• DFS로 해당 섬 전체 탐색 → 방문 처리
• DFS로 섬 탐색 끝나면 섬 개수 ++

 

2 DFS 함수 만들기

void dfs(int y, int x, int end_h, int end_w, vector<vector<int>>& map){
    int dx[] = {0, 0, -1, 1}; // 상, 하, 좌, 우
    int dy[] = {1, -1, 0, 0}; // 상, 하, 좌, 우

    map[y][x] = 0; // 방문처리

    for(int i =0; i<4; ++i){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx>=0 && nx < end_w && ny>=0 && ny < end_h){
            if(map[ny][nx]) dfs(ny, nx, end_h, end_w, map);
        }
    }

    return;
}

// 대각선 고려 안해서 수정해야함

// 대각선 반영
void dfs(int y, int x, int h, int w, vector<vector<int>>& map){
    int dx[] = {0, 0, -1, 1, -1, 1, -1, 1}; // 상, 하, 좌, 우, 대각선(왼위, 오위, 왼아, 오아)
    int dy[] = {1, -1, 0, 0, 1, 1, -1, -1}; // 상, 하, 좌, 우

    map[y][x] = 0; // 방문처리

    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){
            if(map[ny][nx]) dfs(ny, nx, h, w, map);
        }
    }
}

 

 

3. 전체 지도 순회

        int ans = 0;
        
        for(int r = 0; r < h; ++r){
            for(int c = 0; c < w; ++c){
                if(map[r][c]){ // 반복해서 돌다가 1 만나면 dfs 실행
                    dfs(r,c,h,w,map);
                    ans++;
                }
            }
        }

 

4. dfs 흐름 한 번 더 확인

for문 실행

-> 1 만나면 dfs

-> dfs에서 for 문으로 상하좌우대각선 전부 확인  -> 범위 내이고 1이면 dfs로 거기 방문 (방문처리하기)

-> 1다 방문했으면 dfs 탈출

-> ans ++ (섬 개수 세기)

 

5. 코드 전문

#include <iostream>
#include <vector>
using namespace std;

void dfs(int y, int x, int h, int w, vector<vector<int>>& map){
    int dx[] = {0, 0, -1, 1, -1, 1, -1, 1}; 
    int dy[] = {1, -1, 0, 0, 1, 1, -1, -1}; 

    map[y][x] = 0; 

    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){
            if(map[ny][nx]) dfs(ny, nx, h, w, map);
        }
    }
}

int main(){
    int w, h, x;
    while(1){
        cin >> w >> h;
        if(w==0 && h ==0) break;

        vector<vector<int>>map (h,vector<int>(w));
        for(int r = 0; r < h; ++r){
            for(int c = 0; c < w; ++c){
                cin >> x;
                map[r][c] = x;
            }
        }
        
        int ans = 0;
        
        for(int r = 0; r < h; ++r){
            for(int c = 0; c < w; ++c){
                if(map[r][c]){
                    dfs(r,c,h,w,map);
                    ans++;
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}