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

개요

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

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

실버급 BFS/DFS 문제다.

풀이

DFS를 사용해서 풀었다.

입력이 문자열인 점, 모든 위치에서 탐색을 수행해야 된다는 점을 제외하면 기본적인 DFS/BFS 문제와 동일하다.

한 노드에서 시작된 탐색이 끝날 때마다 memset 함수로 visited 배열을 초기화해 줬다.

memset 사용 시 cstring 헤더를 include 하지 않으면 컴파일 에러가 나니 주의해야 한다. 

#include<cstring>
memset(container, value, size);

// example
constexpr int LIMIT = 100;
bool visited[LIMIT][LIMIT]
memset(visited, false, LIMIT*LIMIT*sizeof(bool));

코드

#include<iostream>
#include<cstring>
using namespace std;
constexpr int LIMIT = 102;
constexpr int dy[] = { 0,0,-1,+1 };
constexpr int dx[] = { -1,+1,0,0 };

int T, H, W;
char sheep[LIMIT][LIMIT];
bool visited[LIMIT][LIMIT];
int ans;

void DFS(int y, int x)
{
	for (int i = 0; i < 4; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny == H || ny < 0 || nx == W || nx < 0) continue;
		if (visited[ny][nx]) continue;
		visited[ny][nx] = true;
		if (sheep[ny][nx] != '#') continue;
		DFS(ny, nx);
	}
}

int main()
{
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> H >> W;
		for (int j = 0; j < H; j++)
			for (int k = 0; k < W; k++)
				cin >> sheep[j][k];

		for (int j = 0; j < H; j++)
		{
			for (int k = 0; k < W; k++)
			{
				if (sheep[j][k] != '#' || visited[j][k]) continue;
				DFS(j, k);
				ans++;
			}
		}
		cout << ans << "\n";
		ans = 0;
		memset(visited, false, LIMIT * LIMIT * sizeof(bool));
	}
}