1926 그림

1926 그림

그림의 개수와 가장 큰 그림의 크기를 구하는 문제

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

1743 음식물 피하기와 같이 flood fill의 기초 문제

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

1. 문제

---

간단 설명

가로 세로 사이즈가 주어지고,

N * M 배열에 그림의 정보가 주어진다

1은 그림이 있는 셀, 0은 그림이 없는 셀.

그림의 총 개수와 가장 큰 그림의 크기를 구하는 문제.

연결된 그림은 하나의 그림으로 취급한다

2. 문제 분석

---

필요변수

• 가로, 세로 int N, M
• 그림의 정보를 저장할 map 배열
  • 방문 표시는 따로 필요하지 않을듯
• 4방향을 표기할 direct[4][2] 배열
• 노드 좌표를 표기할 struct node{int y; int x}. ()pair<int, int> 를 써도 상관없을듯)
• 가장 큰 그림의 크기를 저장할 max_size
• 전체 그림의 개수를 저장할 cnt

주의점

• 그림의 크기를 갱신할 때, 언제 1을 증가시킬지 주의
  • 큐에 넣는 노드들은 조건들을 통과한 노드만 삽입하므로, 얘내를 push 또는 pop할 때 1 증가시켜주면 됨

알고리즘

1. N과 M을 입력받고 map[N][M]에 그림 정보를 입력받는다
2. 0,0 부터 시작해서 map[y][x]가 1인지 확인한다(그림이 나오는지 확인)
    2-1. 그림이 나왔다면 현재 셀부터 BFS(y, x)를 돌린다
    2-2. 큐 생성 및 초기화. map[y][x] 를 0으로 처리해서 방문처리한다
    2-3. 큐가 빌때까지 다음을 반복
        2-3-1. 큐의 맨 앞을 꺼내면서 그림의 크기를 1 증가시킨다
        2-3-2. 4방향으로 다음 노드를 탐색한다 ←↑→↓
        2-3-3. 경계를 벗어나면 다음 노드를 확인한다
        2-3-4. 그림이 아닌 셀이라면 다음 노드 확인
        2-3-5. 모든 조건을 통과했다면, 다음에 방문할 노드로 지정하고 (방문처리) 큐에 넣는다
3. BFS를 종료하면 현재 저장된 가장 큰 그림과 크기를 비교 후 갱신한다
4. BFS를 돌릴때마다 그림의 총 개수에 + 1을 해준다. 
    - BFS를 돌리면서 방문한 그림들은 모두 0으로 지워버리기 때문에 BFS의 호출 회수가 총 그림의 개수임
5. 출력 후 종료

3. 소스코드

---

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

#define MAX 501

int N, M;
int map[MAX][MAX];

int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

struct node {
	int y;
	int x;
};
int max_size = 0;

int BFS(int y, int x) {
	queue<node> qu;
	int size = 0;
	map[y][x] = 0;
	qu.push({ y, x });

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();
		size++;

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue;
			if (map[dy][dx] == 0) continue;

			map[dy][dx] = 0;
			qu.push({ dy, dx });

		}
	}
	// cout << size << " ";
	return size;
}

int main() {
	// 입력
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	
	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];
		}
	}

    // BFS
	int cnt = 0;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 1) {
				max_size = max(max_size, BFS(y, x));
				cnt++;
			}
		}
	}
	cout << cnt << '\n' << max_size;

	return 0;
}