백준 : 2667 단지번호붙이기(c++)

백준 링크

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

2667번: 단지번호붙이기

코드 설명

선언 부분

1. 입력값을 담을 char 타입 Board 배열 선언

2. 방문값을 담을 Visit 배열 선언

3. 탐색할 방향 dx, dy 선언

4. 입력할 개수와 구역 개수 구할 변수 선언

 

Board 변수를 char형으로 한 이유는 입력값의 숫자들이 연결되어 있다

숫자가 연결되어 있으면 각 숫자마다 고유번호로 여기는 게 아닌 이어진 숫자 한 개를 의미하게 되어서

char형 배열로 만든 것

 

코드 내부

모든 인덱스 범위만큼을 포문을 돌린다

(모든 인덱스를 돌려도 방문 처리한 구역은 탐색 안 하기 때문 상관없다.)

해당 구역이 방문하지 않은 구역이고 Board가 0이 아닌 구역이면 탐색할 수 있다는 의미

i, j번째를 시작으로 해서 각 방향을 탐색하고 해당 구역의 크기를 체크하면 된다.

 

이때 주의해야 할 점은 방문 체크와 인덱스 범위 체크를 잘해주어야 한다.

코드

#include <iostream>
#include <queue>
#include <string>

char Board[26][26] = {};
int Visit[26][26];

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

using namespace std;

int main(void)
{
    std::cin >> N;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> Board[i][j];
        }
    }

    priority_queue<int, vector<int>, greater<int>> pQ;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (Visit[i][j] == 0 && Board[i][j] != '0')
            {
                // 구역 증가
                ++Count;
                queue<pair<int, int>> qPair;

                qPair.push({ i, j });
                Visit[i][j] = 1;

                int Max = -1;
                int PixelCount = 1;

                while (!qPair.empty())
                {
                    pair<int, int> Cur = qPair.front();
                    qPair.pop();

                    for (int Dir = 0; Dir < 4; ++Dir)
                    {
                        int NextX = Cur.second + dx[Dir];
                        int NextY = Cur.first + dy[Dir];

                        if (Visit[NextY][NextX] == 1 || Board[NextY][NextX] == '0')
                            continue;

                        if (NextX < 0 || NextY < 0 || NextX >= N || NextY >= N)
                            continue;

                        Visit[NextY][NextX] = 1;
                        ++PixelCount;
                        qPair.push({ NextY, NextX });
                    }
                }

                if (PixelCount > 0)
                    pQ.push(PixelCount);
            }
        }
    }
    std::cout << Count << '\n';

    int pQSize = pQ.size();

    for (int i = 0; i < pQSize; ++i)
    {
        std::cout << pQ.top() << '\n';
        pQ.pop();
    }

    return 0;
}