[백준] 1926. 그림

1926. 그림

간단한 dfs, bfs 문제이다.
BFS 너비 우선 탐색으로 문제를 풀었다.

map 이중배열에 그림의 위치를, check 이중 배열에는 확인한 적이 있다면 true 아니면 false.

1. 이중 for문으로 map의 모든 위치를 돌아 그림이 있고, check가 false이면 큐에 좌표를 넣는다.

2. 큐가 빌때까지 상하좌우를 확인하여 그림이고, 확인한적이 없다면 큐에 넣어 bfs를 실행한다.

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

int map[501][501];
bool check[501][501];
int dirY[4] = { 0,0,1,-1 };
int dirX[4] = { 1,-1,0,0 };
int cnt = 0, pic_size = 0;
int n, m;

bool in_map(int y, int x) {
	if (y >= 0 && y < n && x >= 0 && x < m)
		return true;
	return false;
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			cin >> map[i][j];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 1 && !check[i][j]) {
				cnt++;
				int tmp = 0;
				queue<pair<int, int>> q;
				q.push({ i,j });
				check[i][j] = true;
				while (!q.empty()) {
					int y = q.front().first;
					int x = q.front().second;
					tmp++;
					q.pop();
					for (int dir = 0; dir < 4; dir++) {
						int movey = y + dirY[dir], movex = x + dirX[dir];
						if (map[movey][movex] == 1 && !check[movey][movex] && in_map(movey, movex)) {
							q.push({ movey,movex });
							check[movey][movex] = true;
						}
					}
				}
				pic_size = max(pic_size, tmp);
			}
		}
	}
	cout << cnt << " " << pic_size;
}