본문 바로가기
백준 알고리즘/BFS

백준 1012번 C++

by paysmile 2019. 8. 8.


#include 
#include 

using namespace std;
const int MAX = 51;
int n, m, k;
int lettuce[MAX][MAX];
int indexs;
int visited[MAX][MAX];

struct Move {
	int x, y;
};
Move mv[4] = { {-1,0}, {1,0}, {0,1}, {0,-1} };

void dfs(int i, int j) {
	for (int k = 0; k < 4; k++) {
		int movei = i + mv[k].x;
		int movej = j + mv[k].y;
		
		if (movei >= 0 && movei < m && movej >= 0 && movej < n && lettuce[movei][movej] && visited[movei][movej]== 0) {
			visited[movei][movej] = 1;
			lettuce[movei][movej] = indexs;
			dfs(movei, movej);
		}
	}
}

int main(void) {
	int testcase;

	cin >> testcase;
	for (int t = 0; t < testcase; t++) {
		cin >> n >> m >> k;
		memset(lettuce, 0, sizeof(lettuce));
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < k; i++) {
			int x, y;
			cin >> x >> y;
			lettuce[y][x] = 1;
		}
		indexs = 1;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (lettuce[i][j] == 1) {
					indexs++;
					visited[i][j] = 1;
					dfs(i, j);
				}
			}
		}
		cout << indexs-1 << endl;
	}
	return 0;
}

'백준 알고리즘 > BFS' 카테고리의 다른 글

백준 2468번 C++  (0) 2019.08.10
백준 11403번 C++  (0) 2019.08.08
백준 7576번 C++  (0) 2019.08.08
백준 2667번 C++  (0) 2019.08.08
백준 1697번 C++  (0) 2019.08.07