백준 / 바킹독님의 문제집 / 그림(1926)

문제 설명

 

 

문제 해결

 

아직 그래프 자료구조는 잘 모르는 상태이지만

BFS 관련 강의는 어느 정도 들었으므로 문제를 풀어봤다.

바킹독님의 강의에서 BFS 구현의 정석으로 제공해주신 코드를 변수 이름만 나에 맞게 바꿨다.

그림의 개수나 최대 크기 등의 정보를 추가로 알아내야 하는데

기존의 BFS 코드의 이중반복문을 따로 추가하여 검사하고 중간중간 그림의 크기를 비교하는 코드를 넣어서

문제를 해결했다.

 

#include <iostream>
#include <queue>
#include <utility>

#define x first				// first를 x로 별칭
#define y second			// second를 y로 별칭

using namespace std;

int N, M;					// 세로, 가로 길이

int board[500][500];		// 도화지의 색칠 정보
int visit[500][500] {0};	// 각 좌표의 확인 여부 저장

int max_area = 0;			// 가장 넓은 그림의 넓이
int picture_count = 0;		// 그림 개수

queue<pair<int, int>> q;	// BFS 할때 사용하는 큐

pair<int, int> udlr[4] = { {1,0},{0,1},{-1,0},{0,-1} }; // 상하좌우를 탐색할 때 사용하는 페어 배열


int main(int argc, char * argv[]) 
{
	ios_base::sync_with_stdio(false); // 최적화
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> N >> M; // N, M 입력

	for (int i = 0; i < N; i++) // board 정보 입력
		for (int j = 0; j < M; j++)
			cin >> board[i][j];

	
	for (int i = 0; i < N; i++) // BFS 탐색
	{
		for (int j = 0; j < M; j++)
		{
			if ((board[i][j] == 1) && (visit[i][j] == 0)) // 방문하지 않았다고 보드에 그림이 있을 때
			{
				int area = 1; // 현재 탐색 중인 그림의 크기
				picture_count += 1; // 그림의 개수를 늘린다.
				visit[i][j] = 1; // 방문했다고 해주고
				q.push(make_pair(i, j)); // 큐 넣어준다
				while (!q.empty())
				{
					pair<int, int> cur = q.front(); // front 값을 현재 위치로 설정해주고
					q.pop(); // 큐 빼준다.

					for (int k = 0; k < 4; k++) // 상하좌우 4방향 확인
					{
						int nx = cur.x + udlr[k].x; // x 좌표 적용 
						int ny = cur.y + udlr[k].y; // y 좌표 적용

						if (nx < 0 || nx >= N || ny < 0 || ny >= M) // 탐색하려는 좌표가 유효하지 않다면
							continue;

						if ((visit[nx][ny] == 1) || (board[nx][ny] == 0)) // 이미 방문한 좌표이거나, 그림이 없다면
							continue;

						visit[nx][ny] = 1; // nx, ny에 방문 표시
						area += 1;
						q.push(make_pair(nx, ny)); // 큐 넣는다.
					}
				}

				if (max_area < area) // 저장한 최대 크기를 가진 그림보다 더 큰 그림이 있으면
					max_area = area; // 크기를 갱신한다.
			}
		}
	}

	cout << picture_count << '\n'; // 결과 출력
	cout << max_area << '\n';
}