[BOJ] 11183: Coast Length

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

BOJ - Coast Length

문제 유형 : BFS, DFS, 행렬, 구현

문제 난이도 : Silver I

 

문제

The island municipality of Soteholm is required to write a plan of action for their work with emission of greenhouse gases. They realize that a natural first step is to decide whether they are for or against global warming. For this purpose they have read the IPCC report on climate change and found out that the largest effect on their municipality could be the rising sea level.

The residents of Soteholm value their coast highly and therefore want to maximize its total length. For them to be able to make an informed decision on their position in the issue of global warming, you have to help them find out whether their coastal line will shrink or expand if the sea level rises. From height maps they have figured out what parts of their islands will be covered by water, under the different scenarios described in the IPCC report, but they need your help to calculate the length of the coastal lines.

You will be given a map of Soteholm as an N × M grid. Each square in the grid has a side length of 1 km and is either water or land. Your goal is to compute the total length of sea coast of all islands. Sea coast is all borders between land and sea, and sea is any water connected to an edge of the map only through water. Two squares are connected if they share an edge. You may assume that the map is surrounded by sea. Lakes and islands in lakes are not contributing to the sea coast.

 

Soteholm의 섬 지자체는 온실가스 배출에 대한 조치 계획을 작성해야 한다.

그들은 지구 온난화 문제에 대한 자신의 입장에 대해 정보에 입각한 결정을 내릴 수 있으려면, 해안선이 줄어들거나 늘어날지 여부를 알아내도록 도와야 한다.

IPCC 보고서에 설명된 다양한 시나리오에 따라 고도 지도를 통해 섬의 어느 부분이 물로 덮일지 파악했으나, 해안선의 길이를 계산하려면 도움이 필요하다.

 

N x M의 격자 형태의 지도가 젝오된다.

격자의 각 사각형은 변의 길이가 1이고, 물이거나 땅이다.

모든 섬의 해안 전체 길이를 계산하는 것인데, 해안은 육지와 바다의 모든 경계를 의미하며, 바다는 지도의 가장자리와 물로만 연결된 모든 물을 의미한다.

두 개의 사각형이 모서리를 공유하면 연결된 형태이다.

지도가 바다로 둘러싸여 있다고 가정할 수 있고, 호수와 호수 안에 있는 섬은 해안에 기여하지 않는다.

 

 

Figure E.1: Gray squares are land and white squares are water. The thick black line is the sea coast. This example corresponds to Sample Input 1.

 

 

입력

The first line of the input contains two space separated integers N and M where 1 ≤ N, M ≤ 1000. The following N lines each contain a string of length M consisting of only zeros and ones. Zero means water and one means land.

 

입력 첫 째 줄에 N과 M이 주어진다. (1 <= N, M <= 1000.)

이후 N개의 줄로 길이가 M인 숫자 문자열이 주어지는데, 0과 1로만 이루어져있다.

 

0은 물을, 1은 땅을 의미한다.

 

출력

Output one line with one integer, the total length of the coast in km.

출력은 정수 하나인데, 이는 해안의 총 길이이다.

 

풀이

어떻게 전체 둘레를 구하되, 섬 내부에 있는 호수와 호수 안에 있는 섬을 제외시킬 수 있을까?

방법은 간단하다.

밖을 바다로 가정해도 문제없으니, 배열을 (n+2) * (m+2)의 크기로 만들어서 겉은 0으로 한번 더 둘러주면 된다.

 

n과 m을 입력받아서,

1 ~ n행에 1 ~ m열에 값을 넣어주고,

0행 0열부터 바다의 입장에서 bfs를 하면서, 육지를 만날 때마다 둘레의 길이를 1씩 누적해주면 된다.

 

 

코드

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int main()
{
    int n, m;
    int ans = 0;
    cin >> n >> m;

    vector<vector<int>> mat(n + 2, vector<int>(m + 2, 0));

    string s;
    for (int i = 1; i <= n; ++i)
    {   
        cin >> s;
        for (int j = 1; j <= m; ++j)
        {
            mat[i][j] = s[j - 1] - '0';
        }
    }

    queue<pair<int, int>> q;
    q.push({0, 0});
    mat[0][0] = 2;

    while (!q.empty())
    {
        auto curr = q.front();
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int nx = curr.first + dx[i];
            int ny = curr.second + dy[i];

            if (nx < 0 || ny < 0 || nx >= n + 2 || ny >= m + 2)
                continue;
            if (mat[nx][ny] == 1)
            {
                ans++;
                continue;
            }
            if (mat[nx][ny] == 2)
                continue;
            q.push({nx, ny});
            mat[nx][ny] = 2;
        }
    }

    cout << ans << "\n";
    return 0;
}