[구름톤 챌린지] [3주 차 학습 일기] 문제 12 - 발전기

문제

접근 방식

접근하지않은 구역의 최초의 집부터 해당 구역을 모두 탐색하고 다른 구역을 마저 탐색하는 bfs접근 방식을 채택하였습니다

코드

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

int cnt = 0;
int limit;
int ground[1002][1002];
bool visit[1002][1002];
queue<pair<int, int>> check;

int moveRow[4] = {0, 0, 1, -1};
int moveCol[4] = {1, -1, 0, 0};

void cal(int row, int col);

bool isIn(int row, int col);

int main() {
    cin >> limit;


    for (int i = 0; i < limit; ++i) {
        for (int j = 0; j < limit; ++j) {
            int input;
            cin >> input;
            if (input == 1) {
                check.push({i, j});
            }
            ground[i][j] = input;
            visit[i][j] = false;
        }
    }


    while (!check.empty()) {
        while (!check.empty() && visit[check.front().first][check.front().second] == true) {
            check.pop();
        }
        if (!check.empty()) {
            cal(check.front().first, check.front().second);
            cnt++;
            check.pop();
        }
    }

    cout << cnt;
}

void cal(int row, int col) {


    queue<pair<int, int>> q;
    q.push({row, col});

    while (!q.empty()) {
        int firstRow;
        int firstCol;
        tie(firstRow, firstCol) = q.front();
        for (int i = 0; i < 4; ++i) {
            int Row = firstRow + moveRow[i];
            int Col = firstCol + moveCol[i];
            if (isIn(Row, Col) && visit[Row][Col] == false && ground[Row][Col] == 1) {
                visit[Row][Col] = true;
                q.push({Row, Col});
            }
        }
        q.pop();
    }
}


bool isIn(int row, int col) {
    return row >= 0 && col >= 0 && row < limit && col < limit;
}

구름 IDE

https://goor.me/fBinZrb84tbzs9d8A