[BOJ 11234] 양 한마리... 양 두마리... C++

난이도: Silver 2
번호: 11123
생성일: February 22, 2023 4:48 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색
언어: C++

11123번: 양 한마리... 양 두마리...

C++

BFS를 이용한 풀이

#include <iostream>
#include <queue>
using namespace std;

int T, H, W, res = 0;
char node[102][102];
bool visited[102][102];

const int dX[] = {1, -1, 0, 0};
const int dY[] = {0, 0, -1, 1};

void BFS(int i, int j)
{
        // 좌표가 담긴 pair를 담을 queue 생성
    queue<pair<int, int>> Q;
    Q.push({i, j});
    visited[i][j] = true;

    // queue에 남은 값이 없다는건 시작 좌표의 '#'과 연결된 모든 '#'을 탐색했다는 것.
    while (!Q.empty())
    {
        auto p = Q.front();
        Q.pop();

                // 상하좌우 체크
        for (int k = 0; k < 4; k++)
        {
            int x = p.first + dX[k];
            int y = p.second + dY[k];

            if (node[x][y] != '#' || visited[x][y])
                continue;

            Q.push({x, y});
            visited[x][y] = true;
        }
    }
}

// 입력된 값 초기화
void reset()
{
    res = 0;
    for (int i = 0; i < 102; i++)
        for (int j = 0; j < 102; j++)
        {
            node[i][j] = false;
            visited[i][j] = false;
        }
}

int main(void)
{
    cin.tie(0)->ios::sync_with_stdio(0);
    cout.tie(0);

    cin >> T;
    while (T--)
    {
                // 리셋 후 값 입력
        reset();
        cin >> H >> W;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                cin >> node[i + 1][j + 1];

                // 처음부터 끝까지 다 확인해서 '#'이고 방문하지 않은 좌표를 찾아 너비우선탐색 시작.
        for (int i = 1; i <= H; i++)
            for (int j = 1; j <= W; j++)
                if (node[i][j] == '#' && !visited[i][j])
                {
                                        // 너비우선 탐색으로 연결된 모든 #을 찾아 방문체크
                    BFS(i, j);
                    res++;
                }
        cout << res << "\n";
    }
}