[C++] 백준 4963 - 섬의 개수

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

4963번: 섬의 개수

<알고리즘 분류>

   - 그래프 탐색(Graph Search)

   - DFS(Depth First Search)

 

<풀이> 

  1. 한마디로 말하자면, 섬이 몇 덩이(영역)있냐는 것이 문제다.    

  2. 바로 DFS를 떠올렸다. 

 아직 지나치지 않은 땅을 확인하면, 그 주변에 걸어갈 수 있는 땅을 다 찾을때까지 DFS한다. 

 위의 과정을 반복한다. 

 

<주의사항>

  1. DFS는 재귀이므로, 현재 영역의 다음 영역(동서남북+대각선)에 대한 인덱스를 미리 받아야 한다. 이때, 주어진 h*w 배열을 넘어가선 안 된다.

  2. visited[51][51] 배열을 통해 이미 방문했는지 체크해야 한다. 안하면 중복 카운트가 될 수 있다. 

<추천 문제> 

이와 유사한 문제로 1012번 - 유기농 배추 문제가 있다. 두 문제를 꼭 풀어보길 추천한다.

 

<코드>

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int w, h; 
int map[51][51];
bool visited[51][51] = {false,};
int dx[8] = {-1,0,1,0,1, 1, -1,-1}; //시계방향 탐색(대각선까지 탐색)
int dy[8] = {0,1,0,-1,-1,1,1,-1};

void dfs(int y, int x){   //x축, y축
    visited[y][x] = 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){
            if(map[ny][nx] == 1){   //땅이 있다면 
                if(!visited[ny][nx]){   //지나치지 않았다면 
                    dfs(ny, nx); 
                }
            }
        }

        else continue;
    }
}


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

        for (int i=0; i<h; i++){
            for (int j=0; j<w; j++){
                cin >> map[i][j];
            }
        }

        for (int i=0; i<h; i++){
            for (int j=0; j<w; j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    cnt++;
                    dfs(i, j);
                }
            }
        }

        cout << cnt << "\n";
        memset(map, 0, sizeof(map));
        memset(visited, false, sizeof(visited));

    }



}