백준 4963번 C++ 섬의 개수

섬의 개수

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

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다.

푸는 법

DFS 혹은 완전 탐색으로 풀면 된다고 한다.

(i, j)의 위치에서 인접해있는 8개의 위치를 조사해서 탐색해나가면 되는 문제다.

map[i][j]이 0이 아니라면 map[i][j]에 0을 대입하고 주변을 탐색한다.

map[i][j]=0은 이미 방문한 섬이므로 중복을 방지하기 위해서이다.

맞게 푼 것 같았는데 틀렸다면 너비와 높이값을 맞는 위치에 넣었는지 확인해보자.

내가 그래서 틀렸었기 때문이다

ㅠㅠ

코드

#include <iostream>
using namespace std;
int vi[8]={-1, -1, 0, 1, 1, 1, 0, -1};
int vj[8]={0, 1, 1, 1, 0, -1, -1, -1};
void dfs(int map[52][52], int i, int j){
    if(map[i][j]!=0){
        map[i][j]=0;
        for(int m=0; m<8; m++)
            dfs(map, i+vi[m], j+vj[m]);
    }
}
int main(){
    int w, h;
    while(scanf("%d %d", &w, &h)){
        if(w==0&&h==0){
            return 0;
        }
        int map[52][52]={0,};
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++)
                scanf("%d", &map[i][j]);
        }
        int cnt=0;
        for(int i=1; i<=h; i++){
            for(int j=1; j<=w; j++){
                if(map[i][j]==0)
                    continue;
                dfs(map, i, j);
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}