[백준/C,C++] 2667번: 단지번호붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

풀이

hackids.tistory.com/76

[백준/C,C++] 2178번: 미로 탐색

2178번: 미로 탐색에서 발전된 형태의 문제입니다.

 

BFS를 한번만 실행하는게 아니라

 

모든 입력에 대해 실행해야 하고, 총 몇번 BFS가 실행되는지,

 

해당 BFS에서 몇 개의 지점을 방문했는지 세주면 되는 문제입니다.

 

#include<iostream>
#include<queue>
#include<algorithm>

#define py first
#define px second

using namespace std;

const int MAX = 25;

int n;
string arr[MAX];
bool visited[MAX][MAX];
queue <pair<int, int>> q;
pair<int, int> d[4] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
int cnt;
vector<int> res;

void visit(int y, int x)
{
    visited[y][x] = true;
    q.push(pair(y, x));
    cnt++;
}

void BFS()
{
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            if (arr[y][x] == '1' && !visited[y][x]) {
                visit(y, x);
                while (!q.empty()) {
                    pair<int, int> node = q.front();
                    q.pop();
                    for (int i = 0; i < 4; i++) {
                        int ny = node.py + d[i].py;
                        int nx = node.px + d[i].px;
                        if (ny >= 0 && nx >= 0 && ny < n && nx < n) {
                            if (!visited[ny][nx]) {
                                if (arr[ny][nx] == '1') visit(ny, nx);
                                else visited[ny][nx] = true;
                            }
                        }
                    }
                }
                res.push_back(cnt);
                cnt = 0;
            }
        }
    }
}

int main(void)
{
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    BFS();

    sort(res.begin(), res.end());
    size_t sz = res.size();
    cout << sz << '\n';
    for (size_t i = 0; i < sz; i++) {
        cout << res[i] << '\n';
    }
    
    return 0;
}

 

기본적으로 2178번과 비슷한 형태의 코드이지만 모든 지점들이 연결되어 있는게 아니기 때문에,

 

while문을 크게 감싸는 2중 for문이 필요합니다.

반례

Input

8
01100000
00100011
11100000
00001110
00011110
11000110
10000010
11111111

Output

3

2

6

21