[C++] 백준 4963번: 섬의 개수

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

4963번: 섬의 개수

그래프 문제인데. 그냥 동적배열로 재귀형태의 함수로써 풀었다.

별로 효율적이진 않은듯 하다.

주어진 보드판 50*50 의 지도에서 연결된 섬들을 하나하나 지워나가는 방식인데,

그냥 visited 배열을 둬서 방문했다면 아예 섬 갯수를 세는 부분에서 continue 하는 방식이 더 시간이 적게 들 듯 하다.

 

Code

#include <iostream>
#include <string.h>

#define MAX 50
using namespace std;
int row,col = 1;

struct move{
    int x[3] = {-1,0,1};
    int y[3] = {-1,0,1};
};

bool isException(int x,int y)
{
    if(x>=row || y>=col || x < 0 || y < 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void checkArea(bool(* map)[MAX],int w,int h)
{
    struct move move;
    int move_x = 0;
    int move_y = 0;
    for(int i=0; i<3; i++)
    {
        for(int j=0;j<3;j++)
        {
            move_x = w+move.x[i];
            move_y = h+move.y[j];
            if(isException(move_x,move_y)) //  || (i==1 && j==1)
            {
                continue;
            }
            else
            {
                if(map[move_x][move_y])
                {
                    map[move_x][move_y] = false;
                    checkArea(map,move_x,move_y);
                }
            }
            
        }
    }
}

void countIsland(bool(* map)[MAX])
{
    int numberOfIsland = 0;
    for(int w=0; w<row; w++)
    {
        for(int h=0;h<col;h++)
        {
            if(map[w][h])
            {
                map[w][h] = false;
                checkArea(map,w,h);
                numberOfIsland++;
            }
        }
    }
    cout << numberOfIsland<<"\n";
}

int main()
{
    bool map[MAX][MAX] = {false};
    while(1)
    {
        cin >> col >> row;
        if(row==0 && col==0)
        {
            return 0;
        }
        for(int w=0; w<row; w++)
        {
            for(int h=0;h<col;h++)
            {
                cin >> map[w][h];
            }
        }
        countIsland(map);

        for(int i=0; i<MAX; i++)
        {
            memset(map[i], false, sizeof(bool)*MAX); //모든 값 0으로 초기화
        }
    }
    return 0;
}

쓴 라이브러리 함수 중 기억 할 것

memset(배열시작주소,초기화하는 값,sizeof(배열의크기));

 

3번째 인자에는 sizeof(데이터타입)*배열의 길이도 가능하다.

 

배열의 값을 0으로 초기화할 때 유용한 함수.

기억해두자.