[백준 11123번] 양 한마리... 양 두마리... (C++)

문제링크 : https://www.acmicpc.net/problem/11123

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

#include <bits/stdc++.h>
using namespace std;
queue<pair<int ,int>>q;
bool check[101][101];
char c[101][101];
int H, W;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

void bfs(int x, int y)
{
	check[x][y] = 1;  //양이므로 방문 처리
	q.push({ x,y });

	while (!q.empty())
	{
		int xx = q.front().first, yy = q.front().second; q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = xx + dx[i];      //다음 x좌표
			int ny = yy + dy[i];      //다음 y좌표
			if (nx < 0 || ny < 0 || nx >=H || ny >=W) { continue; }  
			if (c[nx][ny]=='#' && check[nx][ny] == 0)   //양이지만, 방문하지 않았다면
			{
				check[nx][ny] = 1;    //방문 처리
				q.push({ nx,ny });    //다음 탐색
			}
		}
	}	
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T, cnt=0;
    cin >> T;

    vector<int> result;

    while(T--)
    {
         cin >> H >> W;
        for(int i=0; i<H; i++)
        {
            for(int j=0; j<W; j++)
            {
                cin >> c[i][j];
            }
        }

        for(int i=0; i<H; i++)
        {
            for(int j=0; j<W; j++)
            {
                if(check[i][j]==0 && c[i][j] == '#')  //양이지만 방문하지않았다면 탐색 시작
                {
                    bfs(i, j);
                    cnt++;                            
                }
            }
        }
        result.push_back(cnt);
        memset(check, 0, sizeof(check));
        cnt=0;
    }
    for(int i=0; i<result.size(); i++)
    {
        cout << result[i] << "\n";
    }
   
    return 0;
}

입력받은 문자 배열과, 방문처리를 확인할 bool 배열 2개를 만든다.

기본적으로 bool 배열은 false이며, 해당 인덱스 값이 양이면 bool 배열도 방문처리를 해준다.

상하좌우 4방향으로 탐색을하며, 해당값도 양이면 bool 배열도 방문처리를 해준다.

양이 아니라면 탐색을 하지 않는다.