[백준/BOJ] 1012번 유기농 배추 (C++)

www.acmicpc.net/problem/1012

1012번: 유기농 배추

전형적인 BFS 유형의 문제였습니다.

세로의 길이를 먼저 입력받는 것을 주의

 

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

int map[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void BFS(int sx, int sy, int m, int n) {
	queue<pair<int, int > > q;
	q.push({ sx, sy });
	map[sx][sy] = 0;
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m || map[nx][ny] == 0) continue;
			q.push({ nx, ny });
			map[nx][ny] = 0;
		}
	}
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T;
    cin >> T;
    while(T--) {
    	int n, m, k, answer = 0;
    	cin >> n >> m >> k;
    	
    	while(k--) {
    		int x, y;
    		cin >> x >> y;
    		map[x][y] = 1;
		}
		
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(map[i][j] == 1) {
					BFS(i, j, m, n);
					answer++;
				}
			}
		}
		
		cout << answer << "\n";
	} 
}