BOJ 1012 : 유기농 배추

[문제]

- M*N배열에 0,1을 입력하고 이어진 1의 묶음을 찾아내는 것

- 아래 그림처럼 이어진 1의 묶음을 세보면 5개 => bfs로 풀자

 

[풀이]

- 기본 bfs알고리즘에서 시작 노드를 for문을 통해 새로 정해주면서 돌린다~

- 이미 방문했거나 0인 노드는 탐색 x

- 주의) 테스트케이스마다 map과 vis를 memset으로 초기화해줘야된다. 까먹고 안했다가 틀림!

 

[코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

#define X first
#define Y second

int M, N, K;
const int MAX = 51;
int map[MAX][MAX];
bool vis[MAX][MAX];
int ans = 0;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};

void bfs(int start_x,int start_y) {
	queue<pair<int, int>>q;
	vis[start_x][start_y] = true;
	q.push({ start_x, start_y });

	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 >= M || ny < 0 || ny >= N)continue;
			if (vis[nx][ny] || map[nx][ny] != 1)continue;

			vis[nx][ny] = true;
			q.push({ nx,ny });
		}
	}
}

int main() {
	int T;
	cin >> T;

	while (T--) {
		cin >> M >> N >> K;
		memset(map, 0, sizeof(map));
		memset(vis, false, sizeof(vis));
		for (int i = 0; i < K; i++) {
			int x, y;
			cin >> x >> y;
			map[x][y] = 1;
		}

		int cnt = 0;
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !vis[i][j]) {
					bfs(i, j);
					cnt++;
				}
			}
		}
		
		cout << cnt << "\n";
	}
	return 0;
}