[C++][백준 BOJ]4963_섬의 개수.

문제 번호

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

4963번: 섬의 개수

 

 

 

알고리즘 분류

 그래프 탐색(BFS)

 

문제 풀이

 BFS를 사용하여 이어진 부분을 모두 탐색하면 된다. 문제에서 최대 높이와 넓이는 각각 50이라고 하여 52*52 크기의 2차원 배열 Graph와 Visited를 사용하였다. 가장 왼쪽 위(1,1)에서 시작하여 (h, w)까지 탐색한다. 탐색 도중 땅(1)을 발견하면 BFS를 실행하여 Visited배열에 하나의 섬을 방문하였다(true)로 표시한다.

 백준 그래프 분류에 많이 있는 유형으로 굳이 다른 점을 뽑자면 4방향 탐색이 아니라 대각선까지 포함된 8방향 탐색을 진행했다는 점이다. 전체적인 로직은 특이하게 다른 점은 없었다.

 

전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

#define MAX 52

//int Graph[MAX][MAX];
//bool Visited[MAX][MAX] = {false};
int dxy[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

void Insert(int w, int h, int Graph[][MAX])
{
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            int num; cin >> num;
            Graph[i][j] = num;
        }
    }
}

void BFS(int y, int x, int Graph[][MAX], bool Visited[][MAX])
{
    queue<pair<int, int>> q;
    q.push({y, x});

    while (!q.empty())
    {
        int curY = q.front().first;
        int curX = q.front().second;
        q.pop();
        Visited[y][x] = true;

        for (int next = 0; next < 8; next++)
        {
            if (!Visited[curY + dxy[next][0]][curX + dxy[next][1]] && Graph[curY + dxy[next][0]][curX + dxy[next][1]])
            {
                q.push({curY + dxy[next][0], curX + dxy[next][1]});
                Visited[curY + dxy[next][0]][curX + dxy[next][1]] = true;
            }
        }
    }
}

int Solution(int w, int h, int Graph[][MAX], bool Visited[][MAX])
{
    int answer = 0;

    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            if (Graph[i][j] == 1 && !Visited[i][j])
            {
                BFS(i, j, Graph, Visited);
                answer++;
            }
        }
    }
    return answer;
}

int main()
{
    int w, h;
    while (1)
    {
        cin >> w >> h;
        if(w==0 && h==0)
            return 0;
        int Graph[MAX][MAX];
        bool Visited[MAX][MAX] = {false};
        memset(Graph,0,sizeof(Graph));
        memset(Visited,false,sizeof(Visited));

        Insert(w, h, Graph);
        cout << Solution(w, h, Graph, Visited) << '\n';
    }
    return 0;
}

특이사항

 문제를 풀면서 간과한 점이 있었다. 배열을 선언할 때 전역 변수로 선언하면 0으로 자동 초기화되지만(아마도 int 형만)

지역변수로 선언할 시에는 따로 초기화를 해주어야 한다. 처음에 그 부분을 헷갈려서 알고리즘을 잘못 짠 줄 알았다. 

문제점을 알고 cstring 헤더 파일을 include 하여서 memset 함수로 Graph 배열과 Visited 배열을 초기화시켰다.

 

void* memset(void* ptr, int value, size_t num)