[알고리즘] C++ 백준 1926 그림

 

백준 1926

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

1926번: 그림

풀이 전 나의 생각

 BFS를 사용할 수 있는지 없는지에 따라 성공, 실패가 나뉠정도로 BFS의 기초적인 내용을 묻는 문제다.

문제의 포인트는 그림이 있는 곳을 방문하여 그림의 개수와 그림의 최대 크기를 구하는 것이다.

1. 그림의  시작점을 방문 하기 위해 for문으로 탐색을 진행한다.
2. 시작점에 도착했다면 BFS를 진행하여 그림의 길이만큼 방문 표시를 해준다
3. 크기는  큐의 pop횟수, 개수는 BFS진입 횟수로 구한다.
4. 다시 1로 돌아가 반복한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>

using namespace std;
int board[502][502];
bool visit[502][502];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
queue<pair<int, int>> q;
int n, m = 0;

int BFS(int x, int y)
{
	int cnt = 0;
	q.push({ x, y });
	visit[x][y] = 1;

	while (!q.empty())
	{
		pair<int, int> p = q.front();
		q.pop();
		cnt++;

		for (int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (visit[nx][ny] || board[nx][ny] != 1) continue;
			
			visit[nx][ny] = 1;
			q.push({ nx, ny });
		}
	}
	return cnt;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int max = 0;
	int num = 0;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> board[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == 1 && visit[i][j] == 0)
			{
				num++;
				int m = BFS(i, j);
				if (max < m)
				{
					max = m;
				}
			}
		}
	}

	cout << num << '\n' << max;
}