[ C++ ] #1926 그림

 

 

어떤식으로 해야할지 알 것 같으면서도...코드로 짜려고하니까 잘 생각이 안난다. 

BFS로 1이 있는한 계속 탐색을 하고 0 으로 둘러쌓이면 탐색을 멈추면된다.

 

그렇게 그림을 하나 찾아내면 그 다음은 어디에서부터 탐색해야할까?

 

---

내가 놓치고 있던게 있었다.

다 0으로 둘러쌓여있으면 Queue는 비기 때문에 BFS는 끝난다. 

 

그럼 그 이후 탐색을 하면서 방문하지 않았고 1인 지점을 찾은 뒤 거기서 부터 다시 BFS를 진행하면된다..!

 

---

BFS 문제를 처음 풀어봐서 조금의 도움을 받았다는게 너무 아쉽고 찝찝하다...

다음에는 무슨일이 있어도 꼭 내 힘으로만 풀어야지!!!!!!!!

 

#include<iostream>
#include<vector>
#include<queue>


using namespace std;

int check[500][500];

int main() {

	int n, m,max=0,num=0;

	int a[500][500];
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] && !check[i][j]) { //방문안했던 1이라면 BFS수행
				int w = 0;
				num++;
				queue<pair<int, int> > Q;
				check[i][j] = 1; // (0, 0)을 방문했다고 명시
				Q.push({ i,j }); // 큐에 시작점인 (0, 0)을 삽입.
				while (!Q.empty()) {
					pair<int, int> cur = Q.front();
					Q.pop();
					w++;
					for (int i = 0; i < 4; i++) {
						int nx = cur.first + dx[i];
						int ny = cur.second + dy[i];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (check[nx][ny] || a[nx][ny] != 1) continue;

						check[nx][ny] = 1; // (nx, ny)를 방문했다고 명시
						Q.push({ nx,ny });
					}
				}
				if (w > max) max = w;
			}
		}
	}

	
	cout << num << "\n" << max;

}