[백준/BOJ] 1926번 그림 (C++)

www.acmicpc.net/problem/1926

1926번: 그림

BFS 유형의 문제였습니다.

프로그래머스의 카카오프렌즈 컬러링북 문제와 거의 동일한 문제입니다. 배열을 탐색하면서 탐색이 완료된 곳의 값을 0으로 바꿔줌으로써 따로 방문 배열을 두지 않았습니다.

 

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int map[501][501];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int BFS(int r, int c) {
	int sum = 1;
	queue<pair<int, int > > q;
	q.push({r, c});
	map[r][c] = 0;
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx <= n && ny >= 0 && ny <= m && map[nx][ny] == 1) {
				q.push({nx, ny});
				map[nx][ny] = 0;
				sum++;
			}
		}
	}
	
	return sum;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for(int i = 0 ; i < n; i++) {
		for(int j = 0 ; j < m; j++) {
			cin >> map[i][j];
		}
	}
	
	int areaCnt = 0, areaSize = 0;
	for(int i = 0 ; i < n; i++) {
		for(int j = 0 ; j < m; j++) {
			if(map[i][j] == 1) {
				int tmp = BFS(i, j);
				areaSize = max(areaSize, tmp);
				areaCnt++;
			}
		}
	}
	
	cout << areaCnt << "\n" << areaSize;
}