[C++][BOJ 백준]2667_단지 번호 붙이기.

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

2667번: 단지번호붙이기

알고리즘 : 그래프 이론.

문제 풀이 :

 DFS/BFS 를 활용하여 이어진 모든 구간의 크기를 구하는 문제이다.

DFS 연습을 위하여 STACK을 사용한 DFS를 구현하여 문제를 해결하였다.

 

 문제에서 주어진 지도를 MAP 이라는 2차원 배열에 저장하였다. 이후 MAP 배열 전체를 탐색하면서 아직 방문하지 않았고(Visited 배열을 사용하여 판별함.), 갈 수 있는 길이면 DFS를 수행하였다. DFS는 이어져있는 모든 정점을 탐색하기 때문에 탐색을 시작하면 한 단지를 모두 탐색하게 된다.

 정점을 방문하여 Visited 배열의 값을 true로 바꿀때 단지의 크기를 측정하는 cnt 변수를 1씩 증가시켰다.

 DFS가 종료되면 단지의 크기를 answer 벡터에 push 한다.

 

코드 : 

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define MAX 27
int Map[MAX][MAX] = {0};
bool Visited[MAX][MAX] = {false};
// 상 우 하 좌
int dxy[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
int N;
// DFS 로 짜야할듯.
vector<int> Solution()
{
    vector<int> answer;
    for (int i = 1; i <= N; i++)
    {
        for (int k = 1; k <= N; k++)
        {
            if (Map[i][k] && !Visited[i][k])
            {
                int cnt = 0;
                stack<pair<int, int>> s;
                s.push({i, k});
                while (!s.empty())
                {
                    int CurY = s.top().first;
                    int CurX = s.top().second;
                    s.pop();
                    if (!Visited[CurY][CurX])
                    {
                        Visited[CurY][CurX] = true;
                        cnt++;
                        for (int j = 0; j < 4; j++)
                        {
                            int nextY = CurY + dxy[j][0];
                            int nextX = CurX + dxy[j][1];
                            if (!Visited[nextY][nextX] && Map[nextY][nextX])
                            {
                                s.push( {nextY, nextX} );
                            }
                        }
                    }
                }
                answer.push_back(cnt);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}
int main()
{
    //cin.tie(NULL);
    //ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        string temp;
        cin >> temp;
        for (int j = 1; j <= N; j++)
        {
            Map[i][j] = temp[j - 1]-'0';
        }
    }
    vector<int> answer;
    answer = Solution();
    cout << answer.size() << '\n';
    for (int i = 0; i < answer.size(); i++)
    {
        cout << answer[i] << '\n';
    }
    return 0;
}