[백준/c++] 4963번 섬의 개수

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

4963번: 섬의 개수

 

문제 해석

1이 입력된 곳(=섬)이 8개의 방향으로 이어져 있으면, 하나의 섬으로 인정한다. 지도에 있는 섬의 총 개수를 출력하는 문제이다.

코드

#include<iostream>
#include<queue>
using namespace std;
struct node{
    int y;
    int x;
};
int map[50][50];
int visited[50][50];
int w,h;
int direct[8][2]={-1,0,
                  1,0,
                  0,-1,
                  0,1,
                  -1,-1,
                  -1,1,
                  1,-1,
                  1,1};
void bfs(int yy, int xx)
{
    queue<node>q;
    q.push({yy,xx});
    visited[yy][xx]=1;
 
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
 
        for(int t=0;t<8;t++)
        {
            int dy= now.y + direct[t][0];
            int dx=now.x + direct[t][1];
 
            if(dy<0 || dx <0 || dy>=h || dx>=w) continue; //범위밖
            if(visited[dy][dx]==1) continue; //재방문 방지
            if(map[dy][dx]==0) continue; // 바다
 
            visited[dy][dx]=1;
            q.push({dy, dx});
        }
    }
}
int main()
{
    while(1)
    {
        int cnt=0;
        cin >> w >> h;
        if(w==0 & h==0) break;
 
        for(int y=0;y<h; y++)
        {
            for(int x=0; x<w; x++)
            {
                cin >> map[y][x];
            }
        }
 
        for(int y=0;y<h; y++)
        {
            for(int x=0; x<w; x++)
            {
                if(map[y][x]==1 && visited[y][x]==0)
                {
                    cnt++;
                    bfs(y,x);
                }
            }
        }
        cout << cnt << '\n';
 
        for(int y=0;y<50; y++)
        {
            for(int x=0;x<50;x++)
            {
                map[y][x]=0;
                visited[y][x]=0;
            }
        }
    }
    return 0;
}

문제 풀이

전역변수로는 섬의 높이와 넓이, 지도 배열, 방문 배열, 방향배열을 만들어 주었다. 그리고 방향의 좌표를 알려줄 구조체도 만들었다. 

main ()함수에서 while문으로 입력을 받고, bfs함수를 호출하고, 초기화 시켜준다. (0,0)이 입력되면 break하여 while문이 끝나게 해주었다.

bfs()함수에서는 1이 입력되어 있는, y좌표와 x좌표를 넘겨주었다. q에 좌표를 push하고, 방문에 1도 표시하였다. 그리고 섬이 더 연결되지 않을 때까지, while문을 도는데 이때, q에 아무것도 남지 않으면 멈추는 조건을 넣어 주었다. node now를 만든 후, q의 맨앞에 있는 값을 넣어준다. 그 다음 q를 pop()해주어 없앤다. 그 다음 8가지의 방향으로 dy, dx의 좌표를 구한다. 이 때, 조건은 재방문 하면 안될 것, 지도 범위 밖을 넘어가면 안될 것, 바다(=0)를 거치면 안될 것 이다. 마지막으로 q에 새로운 좌표값 {dy,dx}를 넣어주고 1이 없을 때 까지,반복한다.