백준 1926

ALGORITHM
2025-09-20

그림

관련 개념

#BFS #플러드 필

문제

1926

📌 1 단계 : 문제 분석하기

  • 해당 문제는 연결된 1들을 찾으면 되는 문제이다.
  • 연결된 1을 찾기 위해서는 BFS를 활용 할 수 있다.
  • 왜 BFS를 써야 할까? → 연결된 1을 찾기 위해서는 인접한 칸들을 계속 방문하면서 면적을 계산해야 함. 이러한 이유로 BFS를 쓴다.

📌 2 단계 : 손으로 풀어보기

  • 0 혹은 이미 방문한 1은 BFS를 시작하지 않는다
  • 그 이외의 1들을 BFS를 시작해서 면적을 계산한다

📌 3 단계 : 슈도 코드 작성하기

📌 4 단계 : 코드 작성하기

#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <numeric>
#include <algorithm> 
#include <set>
#include <tuple>
 
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int dx[] = { -1, 0, 1, 0 };
	int dy[] = { 0, 1, 0, -1 };
 
	int n, m;
	int count = 0;
	int ans = 0;
 
	cin >> n >> m;
 
	vector<vector<int>> arr(n, vector<int>(m, 0));
	vector<vector<bool>> visited(n, vector<bool>(m, false));
 
	for(int i = 0; i < n; i++){
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			
			// 0이나 이미 방문했으면 패스
			if (arr[i][j] == 0 || visited[i][j]) continue;
 
			queue<pair<int, int>> q;
			count++;
 
			// 면적
			int size = 1;
 
			q.push({ i , j });
 
			// 이런 디테일 주의!
			visited[i][j] = true;
 
			while (!q.empty()) {
 
				int cur_x = q.front().first;
				int cur_y = q.front().second;
				q.pop();
 
				for (int k = 0; k < 4; k++) {
					int next_x = cur_x + dx[k];
					int next_y = cur_y + dy[k];
 
					// 범위 안
					if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m) {
 
						if (arr[next_x][next_y] == 1 && !visited[next_x][next_y]) {
							size++;
							visited[next_x][next_y] = true;
							q.push({ next_x, next_y });
						}
 
					}
				}
				
				
			}
			ans = max(ans, size);
		}
	}
 
	cout << count << "\n" << ans;
 
	return 0;
}
 
// 처음에는 오른쪽에서 왼쪽으로 진행하면서, 오른쪽 아래만 큐에 넣으면 된다고
// 생각했는데, 예외 케이스가 있었음!! 항상 예외 케이스 생각하기

📌 5 단계 : 배운점

  • 처음에는 오른쪽에서 왼쪽으로 진행하면서, 오른쪽 아래만 큐에 넣으면 된다고생각했는데, 예외 케이스가 있었음!! 항상 예외 케이스 생각하기
  • 그리고 계속 면적이 1 크게 계산되어서 이상하다 생각했는데, 시작 노드를 방문처리를 안한거였음