알고리즘 ] BFS 알고리즘 (백준 1926 - 그림 문제)

너비 우선 탐색(Breadth First Search)

- 가장 먼저 만나는 인접한 부분들을 전부 탐색하고 전부 탐색 후 그 인접했던 부분에서 다른 인접한 부분들을 탐색하는 방식이다.

 

[알고리즘]

1) 최초 지점을 Queue에 넣는다.

2) Queue에서 하나씩 꺼내옴

3) 꺼내온 데이터를 방문 했음을 표시(별도의 배열 사용)

4) 꺼내온 데이터에서 인접한 노드가 있다면 Queue에 push

5) Queue가 비어질 때까지 2~4를 반복

 

 

백준 1926 - 그림 문제

- 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

 

[문제풀이]

1) 전체 배열을 순회

2) 방문하지 않고 데이터가 '1'인 부분에서 BFS 알고리즘을 수행

   2-1) 해당 지점을 Queue에 넣는다.

   2-2) Queue에서 하나씩 꺼내옴

   2-3) 꺼내온 데이터를 방문 했음을 표시(별도의 배열 사용)하고 갯수를 따로 저장(별도의 vector 사용)

   2-4) 꺼내온 데이터에서 인접한 노드가 있다면 Queue에 push

   2-5) Queue가 비어질 때까지 2~4를 반복

3) 별도의 vector에 저장된 갯수를 정렬

4) vector의 사이즈와 가장 많은 갯수를 출력

 

[*주의 사항]

1) 문제에서 최대 사이즈는 500이었지만 최대 사이즈를 500이 아닌 502로 해야 에러가 발생하지 않음

2) 그림이 하나도 없을 경우를 예외처리 해야함

 

 

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

#define MAX 502

using namespace std;
int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);
	// 변수
	int inputHeight, inputWidth;
	char arr[MAX][MAX];
	bool visited[MAX][MAX];
	fill(&visited[0][0], &visited[MAX-1][MAX-1], false);

	cin >> inputHeight >> inputWidth;

	for(int idxY = 0; idxY < inputHeight; idxY++)
	{
		for (int idxX = 0; idxX < inputWidth; idxX++)
		{
			cin >> arr[idxY][idxX];
		}
	}

	vector<int> result;
	queue<pair<int, int>> q;

	// 전체 순회
	for (int idxY = 0; idxY < inputHeight; idxY++)
	{
		for (int idxX = 0; idxX < inputWidth; idxX++)
		{			
			if (!visited[idxY][idxX] && arr[idxY][idxX] == '1')
			{
				int curSize = 0;
				q.push(make_pair(idxY, idxX));				
				while (!q.empty())
				{
					pair<int, int> front = q.front();
					int y = front.first;
					int x = front.second;

					// 인접한 노드 확인
					if (!visited[y][x])
					{						
						visited[y][x] = true;
						curSize++;
						if (y > 0 & arr[y - 1][x] == '1' && visited[y - 1][x] == false)
						{
							q.push(make_pair(y - 1, x));
						}
						if (x > 0 & arr[y][x - 1] == '1' && visited[y][x - 1] == false)
						{
							q.push(make_pair(y, x - 1));
						}

						if (y < inputHeight - 1 & arr[y + 1][x] == '1' && visited[y + 1][x] == false)
						{
							q.push(make_pair(y + 1, x));
						}
						if (x < inputWidth & arr[y][x + 1] == '1' && visited[y][x + 1] == false)
						{
							q.push(make_pair(y, x + 1));
						}
					}
					q.pop();
				}				
				visited[idxY][idxX] = true;
				result.push_back(curSize);
			}
		}
	}

	// 사이즈가 0인 경우 예외처리
	if (result.size() == 0)
	{
		cout << 0 << endl << 0;
	}
	else
	{
		// 정렬
		sort(result.begin(), result.begin() + result.size());
		cout << result.size() << endl << result.back();
	}


	return 0;
}