백준 1926번: 그림 C++코드

※ 해당 코드의 설명이 맞지 않거나 답이 틀린 경우 댓글로 의견 남겨주시면 수정하겠습니다.

 

관련 알고리즘 : BFS

BFS알고리즘 기초를 학습한 후 직접 짠 코드 입니다. BFS알고리즘 공부는 바킹독님 유튜브를 통해 학습했습니다.

#include <bits/stdc++.h>

using namespace std;
int board[501][501]; //그림 정보
bool vis[501][501]; //방문여부
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 }; //(x,y)의 오른쪽, 위쪽, 왼쪽, 아래쪽 방향
int main() {
	int count = 0;//그림 개수
	int max_area = 0; //최대 넓이
	int n, m; // 가로, 세로 크기
	cin >> n >> m;
	for (int i = 0; i < n; i++) { //board에 그래프 저장
		for (int j = 0; j < m; j++) {
			int a;
			cin >> a;
			board[i][j] = a; //그림정보 저장
		}
	}
	queue<pair<int, int>> Q; 
	for (int i = 0; i < n; i++) { //모든 board 탐색 (전체탐색)
		for (int j = 0; j < m; j++) {
			if (vis[i][j] || board[i][j]==0) continue; //방문했거나 0인 곳은 넘어감
			Q.push({ i,j }); 
			vis[i][j] = 1; //방문 표시
			int area = 0; //해당 그림 넓이
			while (!Q.empty()) { //너비탐색 BFS
				pair<int, int> cur = Q.front(); 
				Q.pop();  //큐 제알 앞 원소 정보 저장 및 pop
				for (int dir = 0; dir < 4; dir++) {
					int x = cur.first + dx[dir];
					int y = cur.second + dy[dir];
					if (vis[x][y] || board[x][y] == 0) continue; //방문했거나 0인 곳은 넘어감
					if (x < 0 || x >= n || y < 0 || y >= m) continue; //범위에 맞지 않은 곳은 넘어감
					Q.push({ x,y }); 
					vis[x][y] = 1; //방문가능한 곳은 큐에 넣고 방문 표시
				}
				area += 1; //방문하였으므로 해당 그림 넓이 1씩 증가
			}
			max_area = max(max_area,area); //최대 넓이 저장
			count += 1; //큐가 모두 비어 더 방문 가능한 곳이 없으므로 그림개수 1씩 증가
		}
	}
	cout << count << endl;
	cout << max_area << endl;
	return 0;
}