백준 1012 : 유기농 배추 (C++, BFS)

https://www.acmicpc.net/problem/1012

 난이도 : 실버2

1012번: 유기농 배추

겁나게 많이 틀렸다...

처음에는 이차원 배열에서 x y 좌표에 대한 이해를 하지 못해서 못 풀었고

다음에는 배열arr 와 배열 check 를 초기화해주지 않아서 틀렸다.

마지막으로는 이차원 배열을 초기화하는 법을 제대로 몰라 틀렸다...

-> 이차원 배열 초기화 fill( &배열[0][0] , &배열[N-1][M] , value ); 

 

 

https://github.com/MongDDangmania/solving_BOJ/blob/main/BFS/1012

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

using namespace std;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0,0,1,-1 };
int arr[51][51] = { 0 };
bool check[51][51] = { false };
int M, N, K; //M: 가로, N: 세로, K: 배추 개수
vector <int> v;

//BFS 수행
void bfs(int j, int i) {  
	pair<int, int> p;
	queue<pair <int, int>> q;
	q.push({ j,i });  //시작 좌표 큐에 넣기
	check[j][i] = true;
	while (!q.empty()) {
		p = q.front();
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = p.second + dx[k], ny = p.first + dy[k];
			if (nx < 0 || nx >= M || ny < 0 || ny >= N) continue; //좌표 범위 벗어나면 넘기기
			if (!arr[ny][nx] || check[ny][nx]) continue; //이미 방문했거나 배추가 없다면 넘기기
			q.push({ ny, nx }); 
			check[ny][nx] = true; 
		}
	}
	return;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		int answer = 0;
		cin >> M >> N >> K;
		for (int i = 0; i < K; i++) {
			int a, b;
			cin >> a >> b;
			arr[b][a] = 1; //배추가 속한 좌표에 1 표시 
		}
		for (int j = 0; j < N; j++) {
			for (int i = 0; i < M; i++) {
				if (arr[j][i] && !check[j][i]) { //해당 좌표에 배추가 있고 방문하지 않았을 경우
					bfs(j, i); //bfs실행
					answer++;
				}
			}
		}
		v.push_back(answer);
		
		fill(&arr[0][0], &arr[50][51], 0); //이차원 배열 초기화 fill( &배열[0][0] , &배열[N-1][M] , value );
		fill(&check[0][0], &check[50][51], 0);

	}
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << endl;
	}
	return 0;
}