BOJ] 14716 - 현수막(충남대학교, 생각하는 프로그래밍 대회 A번)

제한사항

2초, 512MB

 

 

입력

첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250)
두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다.

 

출력

혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.

 

 

풀이 방법

BFS, DFS 구분하지 않고 뭘 하든 될 줄 알았는데 BFS를 사용하니까 메모리 초과가 발생했다.

그래서 방향을 틀어 DFS를 사용해서 문제를 해결했다.

사실 BFS로 문제를 해결할 때, 이미 Queue 안에 들어간 내용을 따로 체크해줬으면 메모리 초과가 발생하지 않았을 것 같다.

 

 

소스코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > board;
int dir[8][2] =
{
{1,0},{0,1},{-1,0},{0,-1},
{1,1},{-1,1},{1,-1},{-1,-1}
};
int M, N;
bool isValid(const int dy, const int dx)
{
	return dy >= 0 && dy < M && dx >= 0 && dx < N;
}
void dfs(int y, int x)
{
	board[y][x] = -1;
	for (int i = 0; i < 8; i++)
	{
		int dy = y + dir[i][0], dx = x + dir[i][1];
		if (isValid(dy, dx) && board[dy][dx] == 1)
			dfs(dy, dx);
	}
}
int main(void)
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	int cnt = 0;
	cin >> M >> N;
	board = vector<vector<int > >(M, vector<int>(N, 0));

	for (int i = 0; i < M; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	for (int y = 0; y < M; y++)
	{
		for (int x = 0; x < N; x++)
		{
			if (board[y][x] == 1)
			{
				dfs(y, x);
				cnt++;
			}
		}
	}
	cout << cnt;
}