[C++] 백준 온라인 저지 4963번 섬의 개수 풀이

지도에 표시되어 있는 섬의 개수를 세는 문제

 

---

문제의 조건

 

1. h의 높이 x w의 너비 크기를 가진 지도가 주어진다. 

 

2. 2차원 지도 배열에는 0과 1로 표시가 되어 있다. 

0은 바다, 1은 땅이라는 뜻

 

3. 2차원 배열의 각 땅들은 상하좌우 대각선으로 연결되면 하나의 섬이라고 할 수 있다. 

 

4. 여러 테스트 케이스가 주어질 때 각 테스트 케이스의 섬의 갯수를 구해서 출력하기 

 

5. 입력의 마지막 줄에는 0 0 이 주어진다. 

입력받은 w와 h가 둘 다 0이라면 테스트 케이스 입력받기 종료하고 프로그램도 종료 

 

---

풀이 과정

 

BFS로 상하좌우에 연속되어 있는 같은 숫자 갯수 세던 문제에서 대각선 방향만 추가해서 풀면 될 거 같아서 

기존 BFS 코드에 대각선 방향만 추가해서 풀었습니다. 

 

1. 방향 확인용 배열에 상하좌우 및 대각선 방향도 추가한다. 

 

2. 무한 반복문으로 w와 h를 입력받은 뒤 그에 맞춰 지도를 세팅하고 BFS로 섬을 탐색한 후

해당 테스트 케이스 탐색이 끝나면 섬의 개수를 출력한다. 

 

3. 입력받은 w와 h의 값이 모두 0이라면 break로 반복문을 종료한다. 

 

---

 

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

using namespace std;

int main(int argc, const char * argv[])
{
    //탐색 방향 (상하좌우 대각선)
    vector<vector<int>> dir;
    dir.push_back({-1,-1});
    dir.push_back({-1,0});
    dir.push_back({-1,1});
    dir.push_back({0,1});
    dir.push_back({1,1});
    dir.push_back({1,0});
    dir.push_back({1,-1});
    dir.push_back({0,-1});
    
    while (true)
    {
        int width, height;
        cin >> width >> height;
        
        //입력받은 너비와 높이가 0이면 반복문 종료 
        if (0 == width && 0 == height)
            break;
        
        vector<vector<bool>> Map(height, vector<bool>(width, false));
        for (int i = 0; height > i; i++)
        {
            for (int j = 0; width > j; j++)
            {
                int flag;
                cin >> flag;
                if (0 != flag)
                    Map[i][j] = true;
            }
        }
        
        int answer = 0;
        vector<vector<bool>> visited(height, vector<bool>(width, false));
        for (int i = 0; height > i; i++)
        {
            for (int j = 0; width > j; j++)
            {
                //BFS로 섬 탐색 
                if (!visited[i][j] && Map[i][j])
                {
                    queue<pair<int, int>> q;
                    q.emplace(make_pair(i, j));
                    
                    visited[i][j] = true;
                    
                    while (!q.empty())
                    {
                        auto curTile = q.front();
                        q.pop();
                        
                        for (int k = 0; dir.size() > k; k++)
                        {
                            auto nextTile = make_pair(curTile.first + dir[k][0], 
                            curTile.second + dir[k][1]);
                            
                            if (0 > nextTile.first || height <= nextTile.first
                                || 0 > nextTile.second || width <= nextTile.second)
                                continue;
                            
                            if (!visited[nextTile.first][nextTile.second] 
                            && Map[nextTile.first][nextTile.second])
                            {
                                q.emplace(nextTile);
                                visited[nextTile.first][nextTile.second] = true;
                            }
                        }
                    }
                    
                    answer++; //섬 하나에 대한 탐색이 끝나면 섬 개수 증가 
                }
            }
        }
        
        cout << answer << endl; //테스트 케이스에 대한 탐색이 끝나면 섬 개수 출력
    }
    
    return 0;
}