백준 c++ 1926번

백준 1926번

 

board는 도화지의 크기를 나타내고 vis는 해당 위치를 방문했는지 나타내고 width에는 각각 그림의 크기를 저장해놓는다.

 

도화지의 세로 크기와 가로 크기 n, m을 입력 받고 도화지에 그림의 정보를 입력한다. 

 

이중 for문을 통해 도화지에 그림이 있는지 확인하고 만약 해당 위치에 방문하지 않았고 도화지에 그림이 있다면 if문으로 들어가 방문했다고 표시를 한 후 큐에 해당 위치를 넣고 count 값을 1 더한다. 그러고 해당 위치로부터 상,하,좌,우 연결된 그림이 있는지 확인한다.

 

마지막으로 width 배열을 내림차순으로 정렬한 후 가장 큰 width[0]을 출력한다.

 

 

 

 

전체 코드

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

using namespace std;

#define X first
#define Y second

int board[502][502] = { 0, };
bool vis[502][502];
int width[62501] = { 0, };
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

bool desc(int a, int b) {
	return a > b;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

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

	queue<pair<int, int>> Q;
	int count = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (vis[i][j] != 1 && board[i][j] == 1) {
				int wid = 0;
				vis[i][j] = 1;
				count++;
				Q.push({ i,j });
				wid++;
				while (!Q.empty()) {
					pair<int, int> cur = Q.front();
					Q.pop();

					for (int dir = 0; dir < 4; dir++) {
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m)
							continue;
						if (vis[nx][ny] || board[nx][ny] != 1)
							continue;
						vis[nx][ny] = 1;
						Q.push({ nx,ny });
						wid++;
					}
				}
				width[count] = wid;
			}
		}
	}
	sort(width, width + count+1, desc);
	cout << count << " " << width[0];
	return 0;
}