[백준] 4963번 섬의 개수 문제풀이

링크 - https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

<문제>

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

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

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

---

<아이디어>

dfs를 사용한 문제이다.

1은 섬이고 0은 바다이다. 

너비와 높이, 지도를 입력받고 탐색하지 않은 섬을 만나면 dfs함수에서 방문여부를 체크하고 dx, dy의 방향으로 모두 탐색을 진행한다. 탐색을 진행하며 또 탐색하지 않은 섬을 만나면 역시 방문여부를 체크해준다.

dfs함수 실행 후 cnt에 1을 더해준다.

입력이 0 0 들어온다면 break를 통해 무한 반복문을 탈출해 종료한다.

---

<소스코드>

 

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

int w,h,cnt,m[51][51];
bool visited[51][51]; //방문체크

int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};//방향(상, 하, 좌, 우, 대각선)

void dfs(int x, int y)
{
    visited[x][y]=true;

    for (int i=0;i<8;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if (ny<0||nx<0||nx>=h||ny>=w) continue;

        if (m[nx][ny]==1&&visited[nx][ny]==false)
        {
            visited[nx][ny]=true;
            dfs(nx, ny);
        }
    }
}

int main()
{
    while (1)
    {
        scanf("%d %d",&w,&h);
        cnt=0;
        for(int i=0;i<h;i++)
        {
            for (int j=0;j<w;j++)
            {
                m[i][j]=0;
                visited[i][j]=false;
            }
        }//초기화

        if(w==0&&h==0) break;
        else
        {
            for (int i=0;i<h;i++)
            {
                for (int j=0;j<w;j++) scanf("%d",&m[i][j]);
            }

            for (int i=0;i<h;i++)
            {
                for (int j=0;j<w;j++)
                {
                    if (m[i][j]==1&&visited[i][j]==false)
                    {
                        dfs(i, j);
                        cnt++;
                    }
                }
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}