[Baekjoon] 1926번: 그림

🥅 문제

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

 

🔍 설계

1로 이루어진 영역의 개수와 넓이를 계산해야 한다. 1로 구성된 어떤 칸에서 가로세로에 인접한 1을 계속해서 추가하여 하나의 영역을 구성해야 하므로, BFS를 사용하면 된다.

 

도화지를 구성하는 칸의 정보를 입력받는다. 한 칸씩 반복문을 통해 순회하면서, 1이라면 그 칸을 한 그림을 이루는 시작점으로 하여 한 그림의 넓이를 반환하는 bfs 함수를 실행한다.

 

방문 여부를 저장하는 visited 배열을 만들 수도 있으나, 공간 복잡도를 줄이기 위해 1이었던 칸을 방문하였으면 0으로 바꾸는 방식으로 작성하였다. 

 

👊 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, max_area = 0, number_of_painting = 0;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
vector<vector<int>> paper(500, vector<int>(500));

int bfs(int start_x, int start_y){
	int cur_area = 1;
	queue<pair<int, int>> q;
	paper[start_x][start_y] = 0;
	q.push({start_x, start_y});
	while (!q.empty()){
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();
		for (int i=0; i<4; i++){
			int new_x = cur_x + dx[i];
			int new_y = cur_y + dy[i];
			if (!(new_x >= 0 && new_x < n && new_y >= 0 && new_y < m)){
				continue;
			}
			if (paper[new_x][new_y] == 1){
				cur_area += 1;
				paper[new_x][new_y] = 0;
				q.push({new_x, new_y});
			}
		}
	}
	return cur_area;
}

int main() {
	cin >> n >> m;
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			cin >> paper[i][j];
		}
	}
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++){
			if (paper[i][j]==1){
				max_area = max(max_area, bfs(i, j));
				number_of_painting += 1;
			}
		}
	}
	cout << number_of_painting << "\n" << max_area << "\n";
	return 0;
}

도화지를 구성하는 칸의 정보를 입력받는다. 한 칸씩 반복문을 통해 순회하면서, 1이라면 그 칸을 한 그림을 이루는 시작점으로 하여 한 그림의 넓이를 반환하는 bfs 함수를 실행한다. 방문 여부를 저장하는 visited 배열을 만들 수도 있으나, 공간 복잡도를 줄이기 위해 1이었던 칸을 방문하였으면 0으로 바꾸는 방식으로 작성하였다. 

 

📝 메모

bfs 함수에서 새로운 칸의 범위를 반드시 확인해야 한다.